1764.md (13457B)
1 Source: https://codeforces.com/blog/entry/109468 2 3 [1764A - Дореми и краски](/contest/1764/problem/A "Codeforces Global Round 24") 4 5 idea: [Cocoly1990](/profile/Cocoly1990 "Мастер Cocoly1990") 6 7 **Solution** 8 9 Tutorial is loading... 10 11 **Code** 12 13 By [Imakf](/profile/Imakf "Международный мастер Imakf") 14 15 ``` 16 #include <iostream> 17 18 void solve(){ 19 int n; std::cin >> n; 20 for(int i = 1 ,nouse ; i <= n ; ++i){ 21 std::cin >> nouse; 22 } 23 std::cout << "1 " << n << std::endl; 24 } 25 26 int main(){ 27 int t; std::cin >> t; 28 while(t--) solve(); 29 return 0; 30 } 31 ``` 32 33 [1764B - Дореми и идеальный урок по математике](/contest/1764/problem/B "Codeforces Global Round 24") 34 35 idea: [waaitg](/profile/waaitg "Международный мастер waaitg") 36 37 **Solution** 38 39 Tutorial is loading... 40 41 **Code** 42 43 By [waaitg](/profile/waaitg "Международный мастер waaitg") 44 45 ``` 46 #include<bits/stdc++.h> 47 using namespace std; 48 const int maxn=100005; 49 int a[maxn]; 50 int gcd(int a,int b){ 51 return b==0?a:gcd(b,a%b); 52 } 53 int main(){ 54 int t;scanf("%d",&t); 55 while(t--){ 56 int n;scanf("%d",&n); 57 int tmp=0; 58 for(int i=1;i<=n;++i){ 59 scanf("%d",&a[i]); 60 tmp=gcd(tmp,a[i]); 61 } 62 printf("%d\n",a[n]/tmp+(a[1]==0)); 63 } 64 return 0; 65 } 66 ``` 67 68 [1764C - Дореми и строительство города](/contest/1764/problem/C "Codeforces Global Round 24") 69 70 idea: [waaitg](/profile/waaitg "Международный мастер waaitg") 71 72 **Solution** 73 74 Tutorial is loading... 75 76 **Code** 77 78 By [waaitg](/profile/waaitg "Международный мастер waaitg") 79 80 ``` 81 #include<cstdio> 82 #include<cstring> 83 #include<iostream> 84 #include<algorithm> 85 #define ch() getchar() 86 #define pc(x) putchar(x) 87 using namespace std; 88 template<typename T>void read(T&x){ 89 static char c;static int f; 90 for(f=1,c=ch();c<'0'||c>'9';c=ch())if(c=='-')f=-f; 91 for(x=0;c>='0'&&c<='9';c=ch()){x=x*10+(c&15);}x*=f; 92 } 93 template<typename T>void write(T x){ 94 static char q[64];int cnt=0; 95 if(x==0)return pc('0'),void(); 96 if(x<0)pc('-'),x=-x; 97 while(x)q[cnt++]=x%10+'0',x/=10; 98 while(cnt--)pc(q[cnt]); 99 } 100 const int maxn=200005; 101 int a[maxn]; 102 int main(){ 103 int t;read(t); 104 while(t--){ 105 int n;read(n); 106 for(int i=1;i<=n;++i) 107 read(a[i]); 108 sort(a+1,a+n+1); 109 if(a[1]==a[n]){ 110 write(n/2),pc('\n'); 111 continue; 112 } 113 long long ans=0; 114 for(int l=1,r=1;l<=n;l=r=r+1){ 115 while(r+1<=n&&a[r+1]==a[l])++r; 116 ans=max(ans,1ll*(n-r)*r); 117 } 118 write(ans),pc('\n'); 119 } 120 return 0; 121 } 122 ``` 123 124 [1764D - Дореми и игра с колышками](/contest/1764/problem/D "Codeforces Global Round 24") 125 126 idea: [Imakf](/profile/Imakf "Международный мастер Imakf") 127 128 **Solution** 129 130 Tutorial is loading... 131 132 **Code** 133 134 By [Imakf](/profile/Imakf "Мастер Imakf") 135 136 ``` 137 #include <cstdio> 138 #include <iostream> 139 140 #define LL long long 141 142 const int MX = 5000 + 233; 143 LL C[MX][MX] ,n ,p ,fac[MX]; 144 145 void init(){ 146 for(int i = 0 ; i < MX ; ++i) C[i][0] = 1; 147 for(int i = 1 ; i < MX ; ++i) 148 for(int j = 1 ; j < MX ; ++j) 149 C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % p; 150 fac[0] = fac[1] = 1 % p; 151 for(int i = 2 ; i < MX ; ++i) fac[i] = fac[i - 1] * i % p; 152 } 153 154 int main(){ 155 std::cin >> n >> p; 156 init(); 157 int t = n / 2; 158 LL Ans = 0; 159 for(int i = t ; i <= n - 1 ; ++i){ 160 if((n & 1) && i == n - 1) break; 161 int upper = (i == n - 1) ? n - i - 1 : n - i - 2; 162 for(int j = 0 ; j <= upper ; ++j){ 163 Ans = (Ans + n * (2 * t - i) * C[upper][j] % p * fac[j + i - 1]) % p; 164 } 165 } 166 std::cout << Ans << std::endl; 167 return 0; 168 } 169 ``` 170 171 [1764E - Дореми и числовая прямая](/contest/1764/problem/E "Codeforces Global Round 24") 172 173 idea: [Imakf](/profile/Imakf "Международный мастер Imakf") 174 175 **Solution** 176 177 Tutorial is loading... 178 179 **Code** 180 181 By [Imakf](/profile/Imakf "Мастер Imakf") 182 183 ``` 184 #include <bits/stdc++.h> 185 186 #define debug(...) fprintf(stderr ,__VA_ARGS__) 187 #define LL long long 188 const int MX = 2e5 + 5; 189 190 int n ,s; 191 struct Goat{ 192 int x ,y ,id; 193 }A[MX]; 194 195 bool cmp(Goat a ,Goat b){ 196 return a.x < b.x; 197 } 198 199 int mx[MX]; 200 int calc(int id){ 201 if(id == 1) return A[id].x; 202 int far = std::max(calc(id - 1) ,mx[id - 2]); 203 return std::max(std::min(far ,A[id].x) + A[id].y ,A[id].x); 204 } 205 206 int ans[MX]; 207 void solve(){ 208 scanf("%d%d" ,&n ,&s); 209 for(int i = 1 ,x ,y ; i <= n ; ++i){ 210 scanf("%d%d" ,&x ,&y); 211 A[i] = (Goat){x ,y ,i}; 212 ans[i] = false; 213 } 214 std::sort(A + 1 ,A + 1 + n ,cmp); 215 for(int i = 1 ; i <= n ; ++i){ 216 mx[i] = std::max(A[i].x + A[i].y ,mx[i - 1]); 217 } 218 for(int i = 1 ; i < n ; ++i){ 219 if(A[i].x + A[i].y >= s){ 220 ans[A[i].id] = true; 221 } 222 } 223 if(calc(n) >= s) ans[A[n].id] = true; 224 puts(ans[1] ? "YES" : "NO"); 225 } 226 227 int main(){ 228 int t; scanf("%d" ,&t); 229 while(t--) solve(); 230 return 0; 231 } 232 ``` 233 234 [1764F - Дореми и экспериментальное дерево](/contest/1764/problem/F "Codeforces Global Round 24") 235 236 idea: [Cocoly1990](/profile/Cocoly1990 "Мастер Cocoly1990") 237 238 **Solution** 239 240 Tutorial is loading... 241 242 **Code** 243 244 By [Imakf](/profile/Imakf "Международный мастер Imakf") 245 246 ``` 247 #include <bits/stdc++.h> 248 249 #define debug(...) fprintf(stderr ,__VA_ARGS__) 250 #define LL long long 251 252 const int MX = 3e3 + 5; 253 254 bool vis[MX]; 255 LL w[MX][MX] ,dis[MX]; 256 257 std::vector<int> e[MX]; 258 259 int size[MX]; 260 void dfs(int x ,int f){ 261 size[x] = 1; 262 for(auto i : e[x]){ 263 if(i == f) continue; 264 dfs(i ,x); 265 size[x] += size[i]; 266 } 267 for(auto i : e[x]){ 268 if(i == f) continue; 269 printf("%d %d %lld\n" ,x ,i ,(w[1][x] - w[1][i]) / size[i]); 270 } 271 } 272 273 int main(){ 274 int n; scanf("%d" ,&n); 275 memset(w ,-0x3f ,sizeof w); 276 for(int i = 1 ; i <= n ; ++i){ 277 for(int j = 1 ; j <= i ; ++j){ 278 scanf("%lld" ,&w[i][j]); 279 w[j][i] = w[i][j]; 280 } 281 } 282 memset(dis ,-0x3f ,sizeof dis); 283 dis[1] = 0; 284 for(int i = 1 ; i <= n ; ++i){ 285 int x = 0; 286 for(int j = 1 ; j <= n ; ++j){ 287 if(!vis[j] && (!x || dis[j] > dis[x])){ 288 x = j; 289 } 290 } 291 //debug("x = %d " ,x); 292 //ans += dis[x]; 293 if(i != 1) for(int j = 1 ; j <= n ; ++j){ 294 if(w[j][x] == dis[x] && vis[j]){ 295 e[x].push_back(j); 296 e[j].push_back(x); 297 //debug("%d %d\n" ,x ,j); 298 } 299 } 300 vis[x] = true; 301 for(int j = 1 ; j <= n ; ++j){ 302 dis[j] = std::max(dis[j] ,w[x][j]); 303 } 304 } 305 //return 0; 306 dfs(1 ,1); 307 return 0; 308 } 309 ``` 310 311 [1764G3 - Дореми и идеальная пара по структурам данных (сложная версия)](/contest/1764/problem/G3 "Codeforces Global Round 24") 312 313 idea: [waaitg](/profile/waaitg "Международный мастер waaitg") 314 315 **Solution** 316 317 Tutorial is loading... 318 319 **G1 Code** 320 321 By [Imakf](/profile/Imakf "Международный мастер Imakf") 322 323 ``` 324 #include <bits/stdc++.h> 325 326 using namespace std; 327 328 #define debug(...) fprintf(stderr, __VA_ARGS__) 329 330 std::map<std::pair<int, int>, int> M; 331 int n; 332 int query(int l, int r, int k = 2) { 333 if (l == r) return 1; 334 if (l == 1 && r == n) { 335 return n / k + 1; 336 } 337 if (k == 2 && M.count(make_pair(l, r))) 338 return M[make_pair(l, r)]; 339 printf("? %d %d %d\n",l ,r, k); 340 fflush(stdout); 341 int x; 342 scanf("%d", &x); 343 if (k == 2) { 344 M[make_pair(l, r)] = x; 345 } 346 return x; 347 } 348 349 void answer(int x) { 350 printf("! %d\n", x); 351 fflush(stdout); 352 exit(0); 353 } 354 355 int main() { 356 scanf("%d", &n); 357 358 int npos = 0; 359 if (n % 2 == 0) { 360 int l = 1, r = n, mid; 361 while (l <= r) { 362 mid = (l + r) >> 1; 363 364 if (query(1, mid, n) == 2) { 365 r = mid - 1; 366 } else { 367 l = mid + 1; 368 } 369 npos = r + 1; 370 } 371 if (npos == 1 || npos == 2) { 372 if (query(2, n, n) == 1) { 373 npos = 1; 374 } else { 375 npos = 2; 376 } 377 } 378 } 379 //answer(npos); 380 //if (n & 1) { 381 int l = 1, r = n - 1, mid; 382 while (l <= r) { 383 debug("[%d ,%d]\n",l ,r); 384 mid = (l + r) >> 1; 385 int lq = 2 * query(1, mid) - (mid - 1 + 1); 386 int rq = 2 * query(mid + 1, n) - (n - (mid + 1) + 1); 387 if (npos) { 388 if (npos <= mid) --lq; 389 else --rq; 390 } 391 if (lq > rq) { 392 r = mid - 1; 393 } else { 394 l = mid + 1; 395 } 396 } 397 // cut [r + 1, r + 2] 398 ++r; 399 // now cut [r, r + 1] 400 answer(r); 401 // } 402 } 403 ``` 404 405 **G3 Code** 406 407 By [waaitg](/profile/waaitg "Международный мастер waaitg") 408 409 ``` 410 #include<cstdio> 411 #include<cstring> 412 #include<iostream> 413 #include<algorithm> 414 using namespace std; 415 int n; 416 int query(int l,int r,int k){ 417 printf("? %d %d %d\n",l,r,k); 418 fflush(stdout);int re;scanf("%d",&re); 419 return re; 420 } 421 void answer(int x){ 422 printf("! %d\n",x); 423 fflush(stdout); 424 } 425 int rt=-1; 426 void divide(int l,int r,int l1,int l2,int r1,int r2){ 427 if(l==r){ 428 answer(l); 429 return; 430 } 431 if(l+1==r){ 432 if(r1==r2+1){ 433 if(query(r,n,2)==r2+1)answer(r); 434 else answer(l); 435 } 436 else if(l1==l2+1){ 437 if(query(1,l,2)==l2+1)answer(l); 438 else answer(r); 439 } 440 else{ 441 if(l>1){ 442 if(query(1,l,n)==2)answer(r); 443 else answer(l); 444 } 445 else{ 446 if(query(r,n,n)==2)answer(l); 447 else answer(r); 448 } 449 } 450 return; 451 } 452 int mid=(l+r)>>1; 453 int L=query(1,mid,2),R=query(mid+1,n,2); 454 if(L*2-mid>R*2-(n-mid))divide(l,mid,L,l2,r1,R); 455 else if(L*2-mid<R*2-(n-mid))divide(mid+1,r,l1,L,R,r2); 456 else{ 457 if(~rt){ 458 if(rt)divide(l,mid,L,l2,r1,R); 459 else divide(mid+1,r,l1,L,R,r2); 460 } 461 if(query(1,mid,n)==2)rt=0,divide(mid+1,r,l1,L,R,r2); 462 else rt=1,divide(l,mid,L,l2,r1,R); 463 } 464 } 465 int main(){ 466 scanf("%d",&n); 467 divide(1,n,n/2+1,0,n/2+1,0); 468 return 0; 469 } 470 ``` 471 472 [1764H - Дореми и краски 2](/contest/1764/problem/H "Codeforces Global Round 24") 473 474 idea: [Imakf](/profile/Imakf "Международный мастер Imakf"), [waaitg](/profile/waaitg "Международный мастер waaitg") and [errorgorn](/profile/errorgorn "Международный гроссмейстер errorgorn") 475 476 **Solution** 477 478 Tutorial is loading... 479 480 **Code** 481 482 By [errorgorn](/profile/errorgorn "Международный гроссмейстер errorgorn") 483 484 ``` 485 #include <bits/stdc++.h> 486 using namespace std; 487 488 #define int long long 489 #define ii pair<int,int> 490 #define iii tuple<int,int,int> 491 #define fi first 492 #define se second 493 #define endl '\n' 494 495 #define pub push_back 496 #define pob pop_back 497 #define puf push_front 498 #define pof pop_front 499 #define lb lower_bound 500 #define ub upper_bound 501 502 #define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) 503 #define all(x) (x).begin(),(x).end() 504 #define sz(x) (int)(x).size() 505 506 mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); 507 508 int n,m,k; 509 ii arr[600005]; 510 int ans[400005]; 511 512 vector<int> uni; 513 int nxt[200005]; 514 int state[200005]; 515 int state2[200005]; 516 517 bool has(int l,int r,set<int> &s){ 518 auto it=s.lb(l); 519 return *it<r; 520 } 521 522 signed main(){ 523 ios::sync_with_stdio(0); 524 cin.tie(0); 525 cout.tie(0); 526 cin.exceptions(ios::badbit | ios::failbit); 527 528 cin>>n>>m>>k; 529 rep(x,0,m) cin>>arr[x].fi>>arr[x].se; 530 rep(x,0,m) arr[x].fi--,arr[x].se--; 531 rep(x,0,2*m) arr[x+m]=arr[x]; 532 533 int l=0; 534 535 while (l<m){ 536 uni={0,n}; 537 rep(x,l,l+2*k) uni.pub(arr[x].fi),uni.pub(arr[x].se+1); 538 sort(all(uni)); uni.erase(unique(all(uni)),uni.end()); 539 rep(x,0,sz(uni)-1) nxt[uni[x]]=uni[x+1]; 540 541 set<ii> s; for (auto it:uni) s.insert({it,it}); //position, color 542 rep(x,0,sz(uni)) state[uni[x]]=state2[uni[x]]=1; 543 544 vector<iii> proc; //time, position, state 545 rep(x,l+k,l+2*k){ 546 if (s.count({arr[x].fi,arr[x].fi}) && state[arr[x].fi]){ 547 proc.pub({x,arr[x].fi,state[arr[x].fi]}); 548 state[arr[x].fi]=0; 549 } 550 551 while (true){ 552 auto it=s.ub(ii(arr[x].fi,1e9)); 553 if ((*it).fi>arr[x].se) break; 554 555 if (arr[x].se+1<(*next(it)).fi) s.insert({arr[x].se+1,(*it).se}); 556 else{ 557 proc.pub({x,(*it).se,state[(*it).se]}); 558 state[(*it).se]=0; 559 } 560 561 s.erase(it); 562 } 563 } 564 565 int curr=0; 566 set<int> pos={n}; 567 for (auto [a,b]:s) if (b!=n){ 568 curr++; 569 if (state[b]) curr+=nxt[b]-b-1; 570 pos.insert(b); 571 } 572 573 s.clear(); for (auto it:uni) s.insert({it,it}); //color, position 574 set<ii> ranges; rep(x,0,sz(uni)-1) ranges.insert({uni[x],uni[x+1]}); 575 576 rep(x,l+k,l){ 577 //merge things 578 auto it=s.lb({arr[x].fi,-1}); 579 vector<int> v={(*it).se}; 580 while ((*it).fi<=arr[x].se){ 581 it=next(it); 582 s.erase(prev(it)); 583 v.pub((*it).se); 584 } 585 586 if (sz(v)>1){ 587 rep(x,0,sz(v)-1){ 588 if (state[v[x]] && state2[v[x]]) curr-=v[x+1]-v[x]-1; 589 state2[v[x]]=0; 590 curr-=has(v[x],v[x+1],pos); 591 ranges.erase({v[x],v[x+1]}); 592 } 593 curr+=has(v[0],v[sz(v)-1],pos); 594 s.insert({arr[x].fi,v[0]}); 595 ranges.insert({v[0],v[sz(v)-1]}); 596 } 597 598 while (!proc.empty() && get<0>(proc.back())==x+k){ 599 int a,b,c; tie(a,b,c)=proc.back(); proc.pob(); 600 if (c){ 601 state[b]=c; 602 if (state[b] && state2[b]) curr+=nxt[b]-b-1; 603 } 604 605 if (!pos.count(b)){ 606 auto it=prev(ranges.ub({b,1e9})); 607 int l,r; tie(l,r)=*it; 608 if (!has(l,r,pos)) curr++; 609 pos.insert(b); 610 } 611 } 612 613 ans[x]=curr; 614 } 615 616 617 l+=k; 618 } 619 620 rep(x,0,m) cout<<ans[x]<<" "; cout<<endl; 621 } 622 ```