1017.md (28369B)
1 Source: https://codeforces.com/blog/entry/61081 2 3 Tutorial is loading... 4 5 **Solution(arsijo)** 6 7 ``` 8 #include <bits/stdc++.h> 9 using namespace std; 10 11 int main() 12 { 13 int n; 14 cin >> n; 15 int a, b, c, d; 16 cin >> a >> b >> c >> d; 17 int S = a + b + c + d; 18 int Ans = 1; 19 for(int i = 2; i <= n; i++) 20 { 21 cin >> a >> b >> c >> d; 22 if(a + b + c + d > S) 23 { 24 Ans++; 25 } 26 } 27 printf("%d\n",Ans); 28 return 0; 29 } 30 ``` 31 32 Tutorial is loading... 33 34 **Solution(arsijo)** 35 36 ``` 37 #include <bits/stdc++.h> 38 using namespace std; 39 40 long long ar[4]; 41 char c1[4] = {'0', '0', '1', '1'}; 42 char c2[4] = {'0', '1', '0', '1'}; 43 44 int main() { 45 int n; 46 cin >> n; 47 string a, b; 48 cin >> a >> b; 49 for(int i = 0; i < n; i++){ 50 for(int j = 0; j < 4; j++){ 51 if(c1[j] == a[i] && c2[j] == b[i]){ 52 ar[j]++; 53 } 54 } 55 } 56 cout << ar[0] * ar[2] + ar[0] * ar[3] + ar[1] * ar[2] << endl; 57 return 0; 58 } 59 ``` 60 61 Tutorial is loading... 62 63 **Solution(Magolor)** 64 65 ``` 66 #include <bits/stdc++.h> 67 using namespace std; 68 #define MAXN 100000 69 #define rint register int 70 inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;} 71 int n, L, A[MAXN+5]; 72 int main() 73 { 74 n = rf(); 75 L = (int)sqrt(n); 76 for(rint i = 1, o = n, j; i <= n; i += L) 77 for(j = min(i+L-1,n); j >= i; A[j--] = o--); 78 for(rint i = 1; i <= n; i++) 79 printf("%d%c",A[i],"\n "[i<n]); 80 return 0; 81 } 82 ``` 83 84 Tutorial is loading... 85 86 **Solution(Magolor)** 87 88 ``` 89 #include <bits/stdc++.h> 90 using namespace std; 91 #define MAXN 100000 92 #define rint register int 93 inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;} 94 int Wu[4096], f[64][64][104], g[4096][104], w[16], m, n, q, E, K, B = 6, L = 63, H = 4032; char _[16]; 95 int main() 96 { 97 m = rf(); 98 n = rf(); 99 q = rf(); 100 generate(w,w+m,rf); 101 E = 1<<m; 102 for(rint S = 0, j; S < E; S++) 103 { 104 for(j = 0; j < m; j++) 105 S&1<<j?:Wu[S]+=w[j]; 106 Wu[S] = min(Wu[S],101); 107 } 108 for(rint i = 1, j, S; i <= n; i++) 109 { 110 scanf("%s",_+1); 111 for(S = 0, j = m; j; j--) 112 S = S<<1|(_[j]^'0'); 113 for(j = 0; j < 64; j++) 114 ++f[(S&H)>>B][j][Wu[((j^(S&L))|H)&~-E]]; 115 } 116 for(rint S = 0, a, b, j; S < E; S++) 117 { 118 for(j = 0; j < 64; j++) 119 for(a = 0, b = Wu[(((j<<B)^(S&H))|L)&~-E]; b <= 100; a++, b++) 120 g[S][b] += f[j][S&L][a]; 121 partial_sum(g[S],g[S]+101,g[S]); 122 } 123 for(rint i = 1, j, S; i <= q; i++) 124 { 125 scanf("%s",_+1); 126 for(S = 0, j = m; j; j--) 127 S = S<<1|(_[j]^'0'); 128 printf("%d\n",g[S][rf()]); 129 } 130 return 0; 131 } 132 ``` 133 134 Tutorial is loading... 135 136 **Solution(Magolor)** 137 138 ``` 139 #include <bits/stdc++.h> 140 using namespace std; 141 #define ll long long 142 #define rint register int 143 inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;} 144 //=====Computational Geometry Definitions 145 struct Vec 146 { 147 int x,y; Vec(){} Vec(int _x, int _y){x=_x,y=_y;} inline Vec operator + (Vec b){return Vec(x+b.x,y+b.y);} 148 inline Vec operator - (Vec b){return Vec(x-b.x,y-b.y);} inline Vec operator - (){return Vec(-x,-y);} 149 inline ll operator * (Vec b){return (ll)x*b.x+(ll)y*b.y;} inline ll operator % (Vec b){return (ll)x*b.y-(ll)b.x*y;} 150 inline ll operator ~ (){return (ll)x*x+(ll)y*y;} inline bool operator < (const Vec &b)const{return x^b.x?x<b.x:y<b.y;} 151 inline bool operator ==(Vec b){return x==b.x&&y==b.y;} inline bool operator !=(Vec b){return x^b.x||y^b.y;} 152 }; typedef Vec Pt; inline bool ToLeft(Vec a, Vec b){return b%a>0;} inline bool Para(Vec a, Vec b){return !(a%b);} 153 Pt LTL; inline bool cmpltl(Pt a, Pt b){a = a-LTL; b = b-LTL; return Para(a,b) ? ~a<~b : ToLeft(b,a);} 154 typedef vector<Pt> Poly; Poly A, B, C, D; typedef vector<ll> Str; Str T, S; int n, m; vector<int> nex; 155 //===== 156 void CH(Poly &A, Poly &R) 157 { 158 R.push_back(Pt()); 159 LTL = *min_element(A.begin(),A.end()); 160 sort(A.begin(),A.end(),cmpltl); 161 for(rint i = 0; i < (int)A.size(); i++) 162 { 163 for(; R.size()>2&&!ToLeft(A[i]-R.back(),R.back()-R[R.size()-2]); ) 164 R.pop_back(); 165 R.push_back(A[i]); 166 } 167 R[0] = R[R.size()-1]; 168 R.push_back(R[1]); 169 } 170 void CTOS(Poly &p, Str &s) 171 { 172 s.push_back(0); 173 for(rint i = 1; i < (int)p.size()-1; i++) 174 { 175 s.push_back(~(p[i]-p[i-1])); 176 s.push_back((p[i]-p[i-1])%(p[i+1]-p[i])); 177 } 178 } 179 void CalNex() 180 { 181 nex.resize(m+1); 182 for(rint i = 2, j = 1; i <= m; i++) 183 { 184 for(; j>1&&S[i]^S[j]; ) 185 j = nex[j-1]+1; 186 j += S[i]==S[j]; 187 nex[i] = j-1; 188 } 189 } 190 bool KMP() 191 { 192 for(rint i = 1, j = 1; i <= n; i++) 193 { 194 for(; j>1&&(j>m||T[i]^S[j]); ) 195 j = nex[j-1]+1; 196 j+=T[i]==S[j]; 197 if(j>m) 198 return true; 199 } 200 return false; 201 } 202 int main() 203 { 204 A.resize(rf()); B.resize(rf()); 205 for(rint i = 0, s = (int)A.size(); i < s; i++) 206 A[i].x = rf(), A[i].y = rf(); 207 CH(A,C); 208 CTOS(C,T); 209 n = T.size()-1; 210 for(rint i = 0, s = (int)B.size(); i < s; i++) 211 B[i].x = rf(), B[i].y = rf(); 212 CH(B,D); 213 CTOS(D,S); 214 m = S.size()-1; 215 for(rint i = 1, s = (int)T.size(); i < s; i++) 216 T.push_back(T[i]); 217 n <<= 1; 218 CalNex(); 219 puts(KMP()?"YES":"NO"); 220 return 0; 221 } 222 ``` 223 224 **Solution(Kostroma)** 225 226 ``` 227 #pragma comment(linker, "/STACK:512000000") 228 #define _CRT_SECURE_NO_WARNINGS 229 //#include "testlib.h" 230 #include <bits/stdc++.h> 231 using namespace std; 232 233 #define all(a) a.begin(), a.end() 234 using li = long long; 235 using ld = long double; 236 void solve(bool); 237 void precalc(); 238 clock_t start; 239 int main() { 240 #ifdef AIM 241 freopen("/home/alexandero/CLionProjects/ACM/input.txt", "r", stdin); 242 //freopen("/home/alexandero/CLionProjects/ACM/output.txt", "w", stdout); 243 //freopen("out.txt", "w", stdout); 244 #else 245 //freopen("input.txt", "r", stdin); 246 //freopen("output.txt", "w", stdout); 247 #endif 248 start = clock(); 249 int t = 1; 250 #ifndef AIM 251 cout.sync_with_stdio(0); 252 cin.tie(0); 253 #endif 254 cout.precision(20); 255 cout << fixed; 256 //cin >> t; 257 precalc(); 258 while (t--) { 259 solve(true); 260 } 261 cout.flush(); 262 263 #ifdef AIM1 264 while (true) { 265 solve(false); 266 } 267 #endif 268 269 #ifdef AIM 270 cerr << "\n\n time: " << (clock() - start) / 1.0 / CLOCKS_PER_SEC << "\n\n"; 271 #endif 272 return 0; 273 } 274 275 //BE CAREFUL: IS INT REALLY INT? 276 277 template<typename T> 278 T binpow(T q, T w, T mod) { 279 if (!w) 280 return 1 % mod; 281 if (w & 1) 282 return q * 1LL * binpow(q, w - 1, mod) % mod; 283 return binpow(q * 1LL * q % mod, w / 2, mod); 284 } 285 286 template<typename T> 287 T gcd(T q, T w) { 288 while (w) { 289 q %= w; 290 swap(q, w); 291 } 292 return q; 293 } 294 template<typename T> 295 T lcm(T q, T w) { 296 return q / gcd(q, w) * w; 297 } 298 299 template <typename T> 300 void make_unique(vector<T>& vec) { 301 sort(all(vec)); 302 vec.erase(unique(all(vec)), vec.end()); 303 } 304 305 template<typename T> 306 void relax_min(T& cur, T val) { 307 cur = min(cur, val); 308 } 309 310 template<typename T> 311 void relax_max(T& cur, T val) { 312 cur = max(cur, val); 313 } 314 315 void precalc() { 316 317 } 318 319 #define int li 320 //const li mod = 1000000007; 321 //using ull = unsigned long long; 322 323 struct Point { 324 int x, y; 325 Point() {} 326 Point(int x, int y) : x(x), y(y) {} 327 Point operator - (const Point& ot) const { 328 return Point(x - ot.x, y - ot.y); 329 } 330 int operator * (const Point& ot) const { 331 return x * ot.y - y * ot.x; 332 } 333 void scan() { 334 cin >> x >> y; 335 } 336 bool operator < (const Point& ot) const { 337 return make_pair(x, y) < make_pair(ot.x, ot.y); 338 } 339 int sqr_len() const { 340 return x * x + y * y; 341 } 342 long double get_len() const { 343 return sqrtl(sqr_len()); 344 } 345 int operator % (const Point& ot) const { 346 return x * ot.x + y * ot.y; 347 } 348 }; 349 350 struct Polygon { 351 vector<Point> hull; 352 Polygon(int n) { 353 vector<Point> points(n); 354 for (int i = 0; i < n; ++i) { 355 points[i].scan(); 356 } 357 sort(all(points)); 358 vector<Point> up, down; 359 for (auto& pt : points) { 360 while (up.size() > 1 && (up[up.size() - 2] - up.back()) * (pt - up.back()) >= 0) { 361 up.pop_back(); 362 } 363 up.push_back(pt); 364 while (down.size() > 1 && (down[down.size() - 2] - down.back()) * (pt - down.back()) <= 0) { 365 down.pop_back(); 366 } 367 down.push_back(pt); 368 } 369 hull = up; 370 for (int i = (int)down.size() - 2; i > 0; --i) { 371 hull.push_back(down[i]); 372 } 373 } 374 int sqr_len(int pos) const { 375 return (hull[(pos + 1) % hull.size()] - hull[pos]).sqr_len(); 376 } 377 int size() const { 378 return (int)hull.size(); 379 } 380 long double get_angle(int pos) const { 381 auto a = hull[(pos + 1) % hull.size()] - hull[pos], b = hull[(pos + hull.size() - 1) % hull.size()] - hull[pos]; 382 long double co = (a % b) / a.get_len() / b.get_len(); 383 return co; 384 } 385 }; 386 387 void solve(bool read) { 388 vector<Polygon> polys; 389 int n[2]; 390 cin >> n[0] >> n[1]; 391 for (int i = 0; i < 2; ++i) { 392 polys.emplace_back(n[i]); 393 } 394 if (polys[0].size() != polys[1].size()) { 395 cout << "NO\n"; 396 return; 397 } 398 vector<long double> all_lens; 399 int m = polys[0].size(); 400 for (int i = 0; i < m; ++i) { 401 all_lens.push_back(polys[0].sqr_len(i)); 402 all_lens.push_back(polys[0].get_angle(i)); 403 } 404 all_lens.push_back(-1); 405 for (int j = 0; j < 2; ++j) { 406 for (int i = 0; i < m; ++i) { 407 all_lens.push_back(polys[1].sqr_len(i)); 408 all_lens.push_back(polys[1].get_angle(i)); 409 } 410 } 411 /*for (int x : all_lens) { 412 cout << x << " "; 413 } 414 cout << "\n";*/ 415 vector<int> p(all_lens.size()); 416 for (int i = 1; i < p.size(); ++i) { 417 int j = p[i - 1]; 418 while (j > 0 && all_lens[i] != all_lens[j]) { 419 j = p[j - 1]; 420 } 421 if (all_lens[i] == all_lens[j]) { 422 ++j; 423 } 424 p[i] = j; 425 if (p[i] == 2 * m) { 426 cout << "YES\n"; 427 return; 428 } 429 } 430 cout << "NO\n"; 431 432 } 433 ``` 434 435 Tutorial is loading... 436 437 **Solution(Magolor,optimized by arsijo)** 438 439 ``` 440 #include <bits/stdc++.h> 441 using namespace std; 442 #define ll long long 443 #define uint unsigned int 444 #define rint register int 445 inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;} 446 bitset<100000032> _b; int n; uint A, B, C, D, Ans; 447 inline uint f(int p){ 448 return((A*p+B)*p+C)*p+D; 449 } 450 inline int cnt(int p, int n){ 451 int r=0; 452 for(;n/=p;r+=n); 453 return r; 454 } 455 inline auto b(int i)->decltype(_b[0]){ 456 return _b[(i&1)&&(i%6!=3)?i/6<<1|((i%6)>1):0]; 457 } 458 inline auto b2(int i)->decltype(_b[0]){ 459 return _b[i/6<<1|1]; 460 } 461 inline auto b3(int i)->decltype(_b[0]){ 462 return _b[i/6<<1]; 463 } 464 465 int main() 466 { 467 n = rf(); 468 A = rf(); 469 B = rf(); 470 C = rf(); 471 D = rf(); 472 _b[0] = 1; 473 Ans = cnt(2,n)*f(2)+cnt(3,n)*f(3); 474 for(rint i = 5, j, z, c, w; i <= n; i += 4){ 475 if(!b2(i)) 476 { 477 Ans += cnt(i,n)*f(i); 478 if(i <= 20000){ 479 w = i + i; 480 c = w % 6; 481 z = (i * i) % 6; 482 if(c == 0){ 483 if(z == 1){ 484 for(j = i * i; j <= n; j += w){ 485 b3(j) = 1; 486 } 487 }else if(z == 5){ 488 for(j = i * i; j <= n; j += w){ 489 b2(j) = 1; 490 } 491 } 492 }else if(c == 2){ 493 if(z == 1){ 494 for(j = i * i; j <= n; j += w){ 495 b3(j) = 1; 496 j += w + w; 497 if(j <= n){ 498 b2(j) = 1; 499 } 500 } 501 }else if(z == 5){ 502 for(j = i * i; j <= n; j += w + w){ 503 b2(j) = 1; 504 j += w; 505 if(j <= n){ 506 b3(j) = 1; 507 } 508 } 509 } 510 }else if(c == 4){ 511 if(z == 1){ 512 for(j = i * i; j <= n; j += w + w){ 513 b3(j) = 1; 514 j += w; 515 if(j <= n){ 516 b2(j) = 1; 517 } 518 } 519 }else if(z == 5){ 520 for(j = i * i; j <= n; j += w){ 521 b2(j) = 1; 522 j += w + w; 523 if(j <= n){ 524 b3(j) = 1; 525 } 526 } 527 } 528 } 529 } 530 } 531 i += 2; 532 if(i <= n && !b3(i)) 533 { 534 Ans += cnt(i,n)*f(i); 535 if(i <= 20000){ 536 w = i + i; 537 c = w % 6; 538 z = (i * i) % 6; 539 if(c == 0){ 540 if(z == 1){ 541 for(j = i * i; j <= n; j += w){ 542 b3(j) = 1; 543 } 544 }else if(z == 5){ 545 for(j = i * i; j <= n; j += w){ 546 b2(j) = 1; 547 } 548 } 549 }else if(c == 2){ 550 if(z == 1){ 551 for(j = i * i; j <= n; j += w){ 552 b3(j) = 1; 553 j += w + w; 554 if(j <= n){ 555 b2(j) = 1; 556 } 557 } 558 }else if(z == 5){ 559 for(j = i * i; j <= n; j += w + w){ 560 b2(j) = 1; 561 j += w; 562 if(j <= n){ 563 b3(j) = 1; 564 } 565 } 566 } 567 }else if(c == 4){ 568 if(z == 1){ 569 for(j = i * i; j <= n; j += w + w){ 570 b3(j) = 1; 571 j += w; 572 if(j <= n){ 573 b2(j) = 1; 574 } 575 } 576 }else if(z == 5){ 577 for(j = i * i; j <= n; j += w){ 578 b2(j) = 1; 579 j += w + w; 580 if(j <= n){ 581 b3(j) = 1; 582 } 583 } 584 } 585 } 586 } 587 } 588 } 589 printf("%u\n",Ans); 590 return 0; 591 } 592 ``` 593 594 **Solution(000000)** 595 596 ``` 597 #include <bits/stdc++.h> 598 599 using namespace std; 600 typedef unsigned int ll; 601 const ll maxn=4e8; 602 const ll maxp=sqrt(maxn)+10; 603 ll f[4][maxp],g[4][maxp]; 604 ll n,m,A,B,C,D,ans,res,tmp,rt; 605 606 ll p1(ll x){ 607 ll y=x+1; if (x%2==0) x/=2; else y/=2; 608 return x*y; 609 } 610 ll p2(ll x){ 611 long long y=x+1,z=x*2+1; 612 if (x%2==0) x/=2; else y/=2; 613 if (z%3==0) z/=3; else if (x%3==0) x/=3; else y/=3; 614 return (ll)x*y*z; 615 } 616 ll p3(ll x){ 617 ll y=p1(x); 618 return y*y; 619 } 620 bool is_prime(ll x){ 621 for (ll i=2;i*i<=x;i++) if (x%i==0) return false; 622 return true; 623 } 624 625 ll solve(ll n) 626 { 627 ll i,j,rt,o[4]; 628 for (m=1;m*m<=n;m++) { 629 f[0][m]=(n/m-1); 630 f[1][m]=(p1(n/m)-1)*C; 631 f[2][m]=(p2(n/m)-1)*B; 632 f[3][m]=(p3(n/m)-1)*A; 633 } 634 for (i=1;i<=m;i++) { 635 g[0][i]=(i-1); 636 g[1][i]=(p1(i)-1)*C; 637 g[2][i]=(p2(i)-1)*B; 638 g[3][i]=(p3(i)-1)*A; 639 } 640 for (i=2;i<=m;i++) { 641 if (g[0][i]==g[0][i-1]) continue; 642 o[0]=1; for (int w=1;w<4;w++) o[w]=o[w-1]*i; 643 for (j=1;j<=min(m-1,n/i/i);j++) 644 for (int w=0;w<4;w++) 645 if (i*j<m) f[w][j]-=o[w]*(f[w][i*j]-g[w][i-1]); 646 else f[w][j]-=o[w]*(g[w][n/i/j]-g[w][i-1]); 647 for (j=m;j>=i*i;j--) 648 for (int w=0;w<4;w++) 649 g[w][j]-=o[w]*(g[w][j/i]-g[w][i-1]); 650 } 651 for (int i=1;i<=m+1;i++) f[0][i]*=D,g[0][i]*=D; 652 rt=0; 653 for (ll i=1;n/i>m;i++) { 654 for (int w=0;w<4;w++) rt+=(f[w][i]-g[w][m]); 655 //cout<<"H"<<rt<<endl; 656 } 657 return rt; 658 } 659 660 int main() 661 { 662 //freopen("input.txt","r",stdin); 663 ll n; cin >> n >> A >> B >> C >> D; 664 ans=solve(n); 665 for (ll i=2;i<=m;i++){ 666 if (is_prime(i)){ 667 res=A*i*i*i+B*i*i+C*i+D; tmp=n; 668 while (tmp){ 669 ans+=res*(tmp/i); 670 tmp/=i; 671 } 672 } 673 } 674 cout << ans << endl; 675 return 0; 676 } 677 ``` 678 679 Tutorial is loading... 680 681 **Solution(arsijo)** 682 683 ``` 684 #include <bits/stdc++.h> 685 using namespace std; 686 687 const int MAX = 1e5 + 10; 688 689 bool black[MAX]; // is it vertex black now 690 vector<int> vec[MAX]; // main edges 691 bool old_black[MAX]; // to remember the tree before block 692 693 const int MAX_BLOCK_SIZE = 600; 694 695 int t[MAX], v[MAX]; // queries 696 697 bool used[MAX]; // is in mini-tree 698 vector<pair<pair<int, int>, int> > v2[MAX]; // mini-tree edges (son, number of white vertices, dist) 699 int push[MAX]; // push of the i-th vertex in mini-tree 700 bool clear[MAX]; // do we need to clear first 701 702 void dfs_1(int pos, int prev = -1, int white = 0, int dist = 0){ 703 if(used[pos]){ 704 if(prev != -1){ 705 v2[prev].push_back(make_pair(make_pair(pos, white), dist)); 706 } 707 for(int a : vec[pos]){ 708 dfs_1(a, pos, 0, 0); 709 } 710 }else{ 711 if(!black[pos]){ 712 white++; 713 } 714 for(int a : vec[pos]){ 715 dfs_1(a, prev, white, dist + 1); 716 } 717 } 718 } 719 720 void make_1(int pos){ 721 if(!black[pos]){ 722 black[pos] = true; 723 return; 724 } 725 push[pos]++; 726 for(auto a : v2[pos]){ 727 if(a.first.second + 1 <= push[pos]){ 728 make_1(a.first.first); 729 } 730 } 731 } 732 733 void make_2(int pos){ 734 black[pos] = false; 735 push[pos] = 0; 736 clear[pos] = true; 737 for(auto &a : v2[pos]){ 738 a.first.second = a.second; 739 make_2(a.first.first); 740 } 741 } 742 743 void dfs_2(int pos, int p = 0, bool cl = false){ 744 if(used[pos]){ 745 p = push[pos]; 746 cl |= clear[pos]; 747 }else{ 748 black[pos] = old_black[pos]; 749 if(cl){ 750 black[pos] = false; 751 } 752 if(!black[pos] && p){ 753 black[pos] = true; 754 p--; 755 } 756 } 757 for(int a : vec[pos]){ 758 dfs_2(a, p, cl); 759 } 760 } 761 762 int main(){ 763 ios_base::sync_with_stdio(); 764 cin.tie(0); 765 cout.tie(0); 766 int n, q; 767 cin >> n >> q; 768 for(int i = 2; i <= n; i++){ 769 int a; 770 cin >> a; 771 vec[a].push_back(i); 772 } 773 for(int i = 1; i <= q; i++){ 774 cin >> t[i] >> v[i]; 775 } 776 int root = 1; 777 for(int i = 1; i <= q; i += MAX_BLOCK_SIZE){ 778 for(int j = 1; j <= n; j++){ 779 used[j] = false; 780 v2[j].clear(); 781 old_black[j] = black[j]; 782 push[j] = 0; 783 clear[j] = false; 784 } 785 for(int j = 0; j < MAX_BLOCK_SIZE && i + j <= q; j++){ 786 used[v[i + j]] = true; 787 } 788 dfs_1(root); 789 for(int j = 0; j < MAX_BLOCK_SIZE && i + j <= q; j++){ 790 int t = ::t[i + j]; 791 int v = ::v[i + j]; 792 if(t == 1){ 793 make_1(v); 794 }else if(t == 2){ 795 make_2(v); 796 }else{ 797 cout << (black[v] ? "black" : "white") << "\n"; 798 } 799 } 800 dfs_2(root); 801 } 802 return 0; 803 } 804 ``` 805 806 Tutorial is loading... 807 808 **Solution(Magolor)** 809 810 ``` 811 #include <bits/stdc++.h> 812 using namespace std; 813 #define MAXN 200000 814 #define MOD 998244353 815 #define rint register int 816 inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;} 817 int n, m, q, B, C, T, fac[MAXN+5], efac[MAXN+5], Ans[MAXN+5], A[MAXN+5], t[MAXN+5], c[MAXN+5]; 818 int mp[MAXN+5], rv[480], h[480][100032], _init[MAXN+5], d[105][100032]; bitset<100032> b[480]; 819 typedef pair<int,int> pii; pii S[MAXN+5]; struct QU{int u,l,r,k,i;}Q[MAXN+5]; 820 inline bool cmpi(const QU &a, const QU &b) 821 { 822 return a.i<b.i; 823 } 824 inline bool cmpm(const QU &a, const QU &b) 825 { 826 return a.u^b.u?a.u<b.u:a.u&1?a.r<b.r:a.r>b.r; 827 } 828 //fastpow 829 inline int fxp(int s, int n=MOD-2){int a=1;for(;n;n&1?a=1ll*a*s%MOD:0,s=1ll*s*s%MOD,n>>=1);return a;} 830 inline void Init(int k) 831 { 832 if(_init[k]) return; 833 _init[k] = ++C; 834 int *D = d[C], s = 1ll*m*k%MOD; 835 D[0] = 1; 836 for(rint i = 1; i <= n; i++) 837 D[i] = 1ll*D[i-1]*(s+i)%MOD; 838 } 839 inline int dxp(int a, int b) 840 { 841 return 1ll*fac[a]*efac[a-b]%MOD; 842 } 843 inline int DXP(int k, int l) 844 { 845 return d[_init[k]][l]; 846 } 847 void insert(int x) 848 { 849 --h[t[x]][c[x]++]; 850 ++h[t[x]][c[x]]; 851 S[++T] = pii(t[x],c[x]); 852 } 853 void erase(int x) 854 { 855 --h[t[x]][c[x]--]; 856 ++h[t[x]][c[x]]; 857 S[++T] = pii(t[x],c[x]); 858 } 859 inline int calc(int k) 860 { 861 int _ = T; T = 0; 862 for(rint i = 1; i <= _; i++) 863 if(!b[S[i].first][S[i].second]&&h[S[i].first][S[i].second]) 864 S[++T] = S[i], b[S[i].first][S[i].second] = 1; 865 int Ans = 1; 866 for(rint i = 1; i <= T; i++) 867 { 868 b[S[i].first][S[i].second] = 0; 869 Ans = 1ll*Ans*fxp(dxp(rv[S[i].first]+k,S[i].second),h[S[i].first][S[i].second])%MOD; 870 } 871 return Ans; 872 } 873 int main() 874 { 875 n = MAXN; 876 for(rint i = fac[0] = 1; i <= n; i++) 877 fac[i] = 1ll*i*fac[i-1]%MOD; 878 efac[n] = fxp(fac[n]); 879 for(rint i = n; i; i--) 880 efac[i-1] = 1ll*i*efac[i]%MOD; 881 n = rf(); 882 m = rf(); 883 q = rf(); 884 B = n/sqrt(q*2/3)+1; 885 for(rint i = 1; i <= n; i++) 886 ++t[A[i]=rf()]; 887 for(rint i = 1, c = 0; i <= n; i++) 888 mp[t[A[i]]]?:rv[mp[t[A[i]]]=++c]=t[A[i]]; 889 for(rint i = 1; i <= m; i++) 890 t[i] = mp[t[i]]; 891 for(rint i = 1, l, r, k; i <= q; i++) 892 { 893 l = rf(); 894 r = rf(); 895 k = rf(); 896 Init(k); 897 Q[i] = {~-l/B,l,r,k,i}; 898 } 899 sort(Q+1,Q+q+1,cmpm); 900 for(rint i = 1; i <= n; i++) 901 ++h[t[A[i]]][0]; 902 for(rint i = 1, l = 1, r = 0; i <= q; i++) 903 { 904 for(; l > Q[i].l; insert(A[--l])); 905 for(; r < Q[i].r; insert(A[++r])); 906 for(; l < Q[i].l; erase(A[l++])); 907 for(; r > Q[i].r; erase(A[r--])); 908 Ans[Q[i].i] = calc(Q[i].k); 909 } 910 sort(Q+1,Q+q+1,cmpi); 911 for(rint i = 1; i <= q; i++) 912 printf("%d\n",1ll*DXP(Q[i].k,n-(Q[i].r-Q[i].l+1))*Ans[i]%MOD); 913 return 0; 914 } 915 ``` 916 917 **Solution(Kostroma)** 918 919 ``` 920 #pragma comment(linker, "/STACK:512000000") 921 #include <bits/stdc++.h> 922 using namespace std; 923 924 #define all(a) a.begin(), a.end() 925 typedef long long li; 926 typedef long double ld; 927 void solve(__attribute__((unused)) bool); 928 void precalc(); 929 clock_t start; 930 #define FILENAME "" 931 932 int main() { 933 #ifdef AIM 934 string s = FILENAME; 935 // assert(!s.empty()); 936 freopen("/home/alexandero/ClionProjects/cryptozoology/input.txt", "r", stdin); 937 //freopen("/home/alexandero/ClionProjects/cryptozoology/output.txt", "w", stdout); 938 #else 939 // freopen(FILENAME ".in", "r", stdin); 940 // freopen(FILENAME ".out", "w", stdout); 941 //freopen("input.txt", "r", stdin); 942 //freopen("output.txt", "w", stdout); 943 #endif 944 start = clock(); 945 int t = 1; 946 #ifndef AIM 947 cout.sync_with_stdio(0); 948 cin.tie(0); 949 #endif 950 precalc(); 951 cout.precision(10); 952 cout << fixed; 953 //cin >> t; 954 int testNum = 1; 955 while (t--) { 956 //cout << "Case #" << testNum++ << ": "; 957 solve(true); 958 } 959 cout.flush(); 960 #ifdef AIM1 961 while (true) { 962 solve(false); 963 } 964 #endif 965 966 #ifdef AIM 967 cout.flush(); 968 auto end = clock(); 969 970 usleep(10000); 971 print_stats(end - start); 972 usleep(10000); 973 #endif 974 975 return 0; 976 } 977 978 template<typename T> 979 T binpow(T q, T w, T mod) { 980 if (!w) 981 return 1 % mod; 982 if (w & 1) 983 return q * 1LL * binpow(q, w - 1, mod) % mod; 984 return binpow(q * 1LL * q % mod, w / 2, mod); 985 } 986 987 template<typename T> 988 T gcd(T q, T w) { 989 while (w) { 990 q %= w; 991 swap(q, w); 992 } 993 return q; 994 } 995 template<typename T> 996 T lcm(T q, T w) { 997 return q / gcd(q, w) * w; 998 } 999 1000 template <typename T> 1001 void make_unique(vector<T>& a) { 1002 sort(all(a)); 1003 a.erase(unique(all(a)), a.end()); 1004 } 1005 1006 template<typename T> 1007 void relax_min(T& cur, T val) { 1008 cur = min(cur, val); 1009 } 1010 1011 template<typename T> 1012 void relax_max(T& cur, T val) { 1013 cur = max(cur, val); 1014 } 1015 1016 void precalc() { 1017 } 1018 1019 #define int li 1020 const int mod = 998244353; 1021 1022 struct Query { 1023 int l, r, id; 1024 }; 1025 1026 vector<int> res; 1027 vector<int> a; 1028 int n; 1029 1030 int TIMER = 0; 1031 const int C = 200500; 1032 int used[C]; 1033 int cur_cnt[C]; 1034 int rev[C]; 1035 map<int, vector<int>> down; 1036 vector<int> init; 1037 1038 void kill(vector<Query>& all_q, int block_size, int k) { 1039 vector<vector<Query>> by_block(n / block_size + 1); 1040 for (auto& cur_q : all_q) { 1041 by_block[cur_q.l / block_size].push_back(cur_q); 1042 } 1043 for (int i = 0; i < by_block.size(); ++i) { 1044 ++TIMER; 1045 auto& q = by_block[i]; 1046 sort(all(q), [&] (const Query& o1, const Query& o2) { 1047 return o1.r < o2.r; 1048 }); 1049 int cur_l = min(n, (i + 1) * block_size); 1050 int cur_r = cur_l; 1051 int cur_prod = 1; 1052 1053 auto add_item = [&] (int val) { 1054 if (used[val] != TIMER) { 1055 used[val] = TIMER; 1056 cur_cnt[val] = 0; 1057 } 1058 int cur_k = k + init[val]; 1059 ++cur_cnt[val]; 1060 cur_prod = cur_prod * (cur_k - cur_cnt[val] + 1) % mod; 1061 }; 1062 auto remove_item = [&] (int val) { 1063 int cur_k = k + init[val]; 1064 cur_prod = cur_prod * rev[cur_k - cur_cnt[val] + 1] % mod; 1065 --cur_cnt[val]; 1066 }; 1067 1068 for (auto& cur_q : q) { 1069 while (cur_r < cur_q.r) { 1070 add_item(a[cur_r++]); 1071 } 1072 while (cur_l > cur_q.l) { 1073 add_item(a[--cur_l]); 1074 } 1075 while (cur_r > cur_q.r) { 1076 remove_item(a[--cur_r]); 1077 } 1078 while (cur_l < cur_q.l) { 1079 remove_item(a[cur_l++]); 1080 } 1081 res[cur_q.id] = cur_prod * down[k][n - cur_q.r + cur_q.l] % mod; 1082 } 1083 } 1084 } 1085 1086 void solve(__attribute__((unused)) bool read) { 1087 for (int i = 1; i < C; ++i) { 1088 rev[i] = binpow(i, mod - 2, mod); 1089 } 1090 int m, Q; 1091 //read = false; 1092 if (read) { 1093 cin >> n >> m >> Q; 1094 } else { 1095 n = 50000; 1096 m = 100000; 1097 Q = 50000; 1098 } 1099 a.resize(n); 1100 init.assign(m, 0); 1101 for (int i = 0; i < n; ++i) { 1102 if (read) { 1103 cin >> a[i]; 1104 --a[i]; 1105 } else { 1106 a[i] = rand() % m; 1107 } 1108 ++init[a[i]]; 1109 } 1110 map<int, vector<Query>> q; 1111 for (int i = 0; i < Q; ++i) { 1112 int l, r, k; 1113 if (read) { 1114 cin >> l >> r >> k; 1115 } else { 1116 do { 1117 l = rand() % n + 1; 1118 r = rand() % n + 1; 1119 } while (l > r); 1120 k = rand() % 100; 1121 } 1122 --l; 1123 q[k].push_back({l, r, i}); 1124 down[k] = vector<int>(); 1125 } 1126 res.assign(Q, 0); 1127 for (auto& item : down) { 1128 int init_val = (item.first * m) % mod; 1129 auto& vec = item.second; 1130 vec.assign(n + 1, 1); 1131 for (int i = 1; i < vec.size(); ++i) { 1132 vec[i] = vec[i - 1] * (init_val + i) % mod; 1133 } 1134 } 1135 for (auto& item : q) { 1136 int k = item.first; 1137 auto& cur_q = item.second; 1138 int block_size = std::max((int)(n / sqrt((int)cur_q.size())), 1LL); 1139 kill(cur_q, block_size, k); 1140 } 1141 1142 for (int i = 0; i < Q; ++i) { 1143 cout << res[i] << "\n"; 1144 } 1145 1146 } 1147 ``` 1148 1149 ### Bonus Problem 1150 1151 It is the previous D1E and its standard solution is hacked. Can you solve it? 1152 1153 **Bonus problem** 1154 1155 **Legend** 1156 1157 How can the man in the high castle, Abendsen, escape so many times? Because he has a full plan of escaping —— with his films. 1158 1159 The map of the cities can be described as a tree (i.e. connected graph with *n* vertices and *n* - 1 edges) rooted at node 1 —— where Abenden lives. 1160 1161 When he starts his escaping, he plans **at most** *k* travels: one travel is a simple path between two (not necessarily different) vertices. So he goes from 1 to some vertex *v*1, and then goes from *v*1 to *v*2, and so on ... 1162 1163 When he is visiting a vertex (even though he has visited this vertex before) he will get some films. But in some vertexes, he has to give some films. Note that Abendsen \textbf{can} have a negative amount of films. But after every travel, he **has to have a non-negative amount of films**. Note that when Abendsen is starting a new travel, **he is visiting the starting vertex too**. It sounds weird but it is a different world! 1164 1165 At first, Abendsen does not have any films. 1166 1167 He wants to maximize the number of the films he gets after the escape. So please help him find out the maximized films number he can get. 1168 1169 **Input Format** 1170 1171 The first line two contains two integers *n* and *k* (1 ≤ *n* ≤ 1000, 1 ≤ *k* ≤ 106) —— the number of vertices and the maximum number of travels allowed. 1172 1173 The second line contains *n* integers *w*1, *w*2, ..., *w**n* (|*w**i*| ≤ 108) —— how many films will Abendsen get (or give if *w**i* is negative) if he visits the *i*-th vertex. 1174 1175 Each of the next *n* - 1 lines contains two integers *u**i* and *v**i* (1 ≤ *u**i*, *v**i* ≤ *n*, *u**i* ≠ *v**i*) —— vertices connected by the *i*-th edge. 1176 1177 It is guaranteed that the input data describes a correct tree. 1178 1179 **Output Format** 1180 1181 Print one integer, the maximum number of films he can get.