codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```