1439.md (19970B)
1 Source: https://codeforces.com/blog/entry/84731 2 3 We want to mention [BamiTorabi](/profile/BamiTorabi "Expert BamiTorabi") who we thank for helping us with translating the problems and writing the tutorials, and also we apologize for div1 A2 and B hopefully you will forgive us :( . 4 5 Tutorial is loading... 6 7 Prepared by [Mohammad.H915](/profile/Mohammad.H915 "Master Mohammad.H915") Editorial by [Mehrdad_Sohrabi](/profile/Mehrdad_Sohrabi "Grandmaster Mehrdad_Sohrabi") 8 9 **official solution** 10 11 ``` 12 // In The Name Of Allah 13 #include <bits/stdc++.h> 14 #define ss second 15 #define ff first 16 #define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0) 17 #define ret(n) return cout << n, 0 18 #define se(n) cout << setprecision(n) << fixed 19 #define pb push_back 20 #define ll long long 21 #define ld long double 22 //#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops") 23 //#pragma GCC optimize("no-stack-protector,fast-math") 24 //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") 25 using namespace std; 26 27 const int N = 3e5 + 100, OO = 1e9 + 7, T = 50, M = 1e9 + 7, P = 6151, SQ = 280, lg = 20; 28 typedef pair <int, int> pii; 29 30 void solve() { 31 int n, c0, c1, t; 32 string s; 33 cin >> n >> c0 >> c1 >> t >> s; 34 int ans = 0; 35 for(auto u : s) { 36 if(u == '0') 37 ans += min(c0, c1 + t); 38 else 39 ans += min(c1, c0 + t); 40 } 41 cout << ans << endl; 42 } 43 44 int32_t main() { 45 int t; 46 cin >> t; 47 while(t--) 48 solve(); 49 return 0; 50 } 51 ``` 52 53 Tutorial is loading... 54 55 Prepared by [Mohammad.H915](/profile/Mohammad.H915 "Master Mohammad.H915") Editorial by [Mehrdad_Sohrabi](/profile/Mehrdad_Sohrabi "Grandmaster Mehrdad_Sohrabi") 56 57 **official solution** 58 59 ``` 60 #include <bits/stdc++.h> 61 typedef long long int ll; 62 typedef long double ld; 63 #define pb push_back 64 #define pii pair < int , int > 65 #define F first 66 #define S second 67 #define endl '\n' 68 #define int long long 69 #define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) 70 #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") 71 #define kill(x) return cout<<x<<'\n', 0; 72 using namespace std; 73 const int N=2e5+100; 74 ll a[N]; 75 int Main(){ 76 ll n, k; 77 cin >> k >> n; 78 for (int i=1;i<=n*k;i++){ 79 cin >> a[i]; 80 } 81 ll x=(k+1)/2 - 1; 82 x = k - x; 83 ll z=n*k+1; 84 ll ans=0; 85 while(n--){ 86 z-=x; 87 if (z<=0) break; 88 ans+=a[z]; 89 } 90 cout << ans << endl; 91 } 92 int32_t main(){ 93 ll t; 94 cin >> t; 95 while(t--){ 96 Main(); 97 } 98 } 99 ``` 100 101 Tutorial is loading... 102 103 Prepared by [Mohammad.H915](/profile/Mohammad.H915 "Master Mohammad.H915") Editorial by [Mehrdad_Sohrabi](/profile/Mehrdad_Sohrabi "Grandmaster Mehrdad_Sohrabi") 104 105 **official solution** 106 107 ``` 108 // In The Name Of Allah 109 #include <bits/stdc++.h> 110 #define ss second 111 #define ff first 112 #define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0) 113 #define ret(n) return cout << n, 0 114 #define se(n) cout << setprecision(n) << fixed 115 #define pb push_back 116 #define ll long long 117 #define ld long double 118 #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops") 119 #pragma GCC optimize("no-stack-protector,fast-math") 120 //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") 121 using namespace std; 122 123 const int N = 200, OO = 1e9 + 7, T = 50, M = 1e9 + 7, P = 6151, SQ = 280, lg = 20; 124 typedef pair <int, int> pii; 125 char c[N][N]; 126 bool cnt[N][N]; 127 128 struct node {int x1, y1, x2, y2, x3, y3;} p[5]; 129 vector <node> v; 130 131 void upd(int x, int y, int tp, bool is) { 132 if(is) 133 v.pb({x + p[tp].x1, y + p[tp].y1, x + p[tp].x2, y + p[tp].y2, x + p[tp].x3, y + p[tp].y3}); 134 else 135 cnt[x + p[tp].x1][y + p[tp].y1] ^= 1, cnt[x + p[tp].x2][y + p[tp].y2] ^= 1, cnt[x + p[tp].x3][y + p[tp].y3] ^= 1; 136 } 137 138 void solve() { 139 int n, m, od = 0; 140 v.clear(); 141 cin >> n >> m; 142 for(int i = 1; i <= n; i++) { 143 for(int j = 1; j <= m; j++) { 144 cin >> c[i][j]; 145 if(c[i][j] == '1') 146 od++, cnt[i][j] = true; 147 else 148 cnt[i][j] = false; 149 } 150 } 151 if(od == 0) { 152 cout << 0 << endl; 153 return; 154 } 155 if(n == 1 || m == 1) { 156 cout << -1 << endl; 157 return; 158 } 159 for(int i = 1; i <= n - 2; i++) { 160 for(int j = 1; j <= m; j++) { 161 if(cnt[i][j]) { 162 if(j != m) { 163 v.pb({i, j, i + 1, j, i + 1, j + 1}); 164 cnt[i][j] ^= 1, cnt[i + 1][j] ^= 1, cnt[i + 1][j + 1] ^= 1; 165 } 166 else { 167 v.pb({i, j, i + 1, j, i + 1, j - 1}); 168 cnt[i][j] ^= 1, cnt[i + 1][j] ^= 1, cnt[i + 1][j - 1] ^= 1; 169 } 170 } 171 } 172 } 173 for(int i = 1; i <= m - 2; i++) { 174 if(cnt[n - 1][i]) { 175 v.pb({n - 1, i, n - 1, i + 1, n, i + 1}); 176 cnt[n - 1][i] ^= 1, cnt[n - 1][i + 1] ^= 1, cnt[n][i + 1] ^= 1; 177 } 178 if(cnt[n][i]) { 179 v.pb({n, i, n - 1, i + 1, n, i + 1}); 180 cnt[n][i] ^= 1, cnt[n - 1][i + 1] ^= 1, cnt[n][i + 1] ^= 1; 181 } 182 } 183 for(int msk = 0; msk < (1 << 4); msk++) { 184 for(int j = 0; j < 4; j++) 185 if(msk & (1 << j)) 186 upd(n - 1, m - 1, j, 0); 187 if(!cnt[n - 1][m - 1] && !cnt[n - 1][m] && !cnt[n][m - 1] && !cnt[n][m]) { 188 for(int j = 0; j < 4; j++) 189 if(msk & (1 << j)) 190 upd(n - 1, m - 1, j, 1); 191 break; 192 } 193 for(int j = 0; j < 4; j++) 194 if(msk & (1 << j)) 195 upd(n - 1, m - 1, j, 0); 196 } 197 cout << (int)v.size() << endl; 198 for(auto u : v) 199 cout << u.x1 << " " << u.y1 << " " << u.x2 << " " << u.y2 << " " << u.x3 << " " << u.y3 << endl; 200 } 201 202 int32_t main(){ 203 use_fast; 204 p[0] = {0, 0, 0, 1, 1, 0}, p[1] = {0, 1, 0, 0, 1, 1}, p[2] = {1, 0, 1, 1, 0, 0}, p[3] = {1, 1, 0, 1, 1, 0}; 205 int t; 206 cin >> t; 207 while(t--) 208 solve(); 209 return 0; 210 } 211 ``` 212 213 Tutorial is loading... 214 215 Prepared by [AliShahali1382](/profile/AliShahali1382 "International Grandmaster AliShahali1382") Editorial by [Amoo_Safar](/profile/Amoo_Safar "International Grandmaster Amoo_Safar") 216 217 **official solution** 218 219 ``` 220 // In The Name Of Allah 221 #include <bits/stdc++.h> 222 #define ss second 223 #define ff first 224 #define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0) 225 #define se(n) cout << setprecision(n) << fixed 226 #define pb push_back 227 //#define int long long 228 #define ld long double 229 #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops") 230 #pragma GCC optimize("no-stack-protector,fast-math") 231 #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") 232 using namespace std; 233 const int N = 1e5 + 100, OO = 1e9 + 7, T = 22, M = 1e9 + 7, P = 6151, SQ = 1300, lg = 22; 234 typedef pair <int, int> pii; 235 int mark[N], deg[N], ct[N]; 236 bool ans[N], can[N]; 237 vector <int> v[N], A; 238 vector <pii> ch[N]; 239 bool cmp(int x, int y) { 240 return mark[x] < mark[y]; 241 } 242 243 void solve() { 244 int n, m, k; 245 cin >> n >> m >> k; 246 A.clear(); 247 for(int i = 0; i <= n; i++) 248 v[i].clear(), ch[i].clear(), mark[i] = deg[i] = ct[i] = 0, ans[i] = can[i] = false; 249 for(int i = 0; i < m; i++) { 250 int x, y; 251 cin >> x >> y; 252 v[x].pb(y); 253 v[y].pb(x); 254 } 255 if(k > 500) { 256 cout << -1 << endl; 257 return; 258 } 259 set <pii> st; 260 for(int i = 1; i <= n; i++) 261 st.insert({deg[i] = (int)v[i].size(), i}); 262 int cnt = 1; 263 while((int)st.size()) { 264 pii p = *st.begin(); 265 if(p.ff >= k) { 266 cout << 1 << " " << (int)st.size() << endl; 267 for(auto u : st) 268 cout << u.ss << " "; 269 cout << endl; 270 return; 271 } 272 else { 273 st.erase(p); 274 mark[p.ss] = cnt; 275 for(auto u : v[p.ss]) 276 if(!mark[u]) 277 st.erase({deg[u], u}), st.insert({--deg[u], u}); 278 A.pb(p.ss); 279 } 280 cnt++; 281 } 282 for(auto i : A) { 283 int nxt = 0; 284 for(auto u : v[i]) 285 if(mark[u] > mark[i]) 286 ct[nxt++] = u, can[u] = true; 287 for(auto u : ch[i]) 288 if(!can[u.ff]) 289 ans[u.ss] = false; 290 for(int j = 0; j < nxt; j++) 291 can[ct[j]] = false; 292 if(nxt != k - 1) 293 continue; 294 ans[i] = true; 295 sort(ct, ct + nxt, cmp); 296 for(int j = 0; j < nxt; j++) 297 for(int k = j + 1; k < nxt; k++) 298 ch[ct[j]].pb({ct[k], i}); 299 } 300 for(auto i : A) { 301 if(!ans[i]) 302 continue; 303 cout << 2 << endl; 304 cout << i << " "; 305 for(auto u : v[i]) 306 if(mark[u] > mark[i]) 307 cout << u << " "; 308 cout << endl; 309 return; 310 } 311 cout << -1 << endl; 312 return; 313 } 314 315 int32_t main() { 316 use_fast; 317 int t; 318 cin >> t; 319 while(t--) 320 solve(); 321 return 0; 322 } 323 ``` 324 325 Tutorial is loading... 326 327 prepared by [Mehrdad_Sohrabi](/profile/Mehrdad_Sohrabi "Grandmaster Mehrdad_Sohrabi") Editorial by [Mehrdad_Sohrabi](/profile/Mehrdad_Sohrabi "Grandmaster Mehrdad_Sohrabi") 328 329 **official solution** 330 331 ``` 332 #include <bits/stdc++.h> 333 #pragma GCC optimize ("O2,unroll-loops") 334 #pragma GCC optimize("no-stack-protector,fast-math") 335 //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") 336 337 using namespace std; 338 typedef long long ll; 339 typedef long double ld; 340 typedef pair<int, int> pii; 341 typedef pair<pii, int> piii; 342 typedef pair<ll, ll> pll; 343 #define debug(x) cerr<<#x<<'='<<(x)<<endl; 344 #define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl; 345 #define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl; 346 #define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;} 347 #define all(x) x.begin(), x.end() 348 #define pb push_back 349 #define kill(x) return cout<<x<<'\n', 0; 350 351 const int inf=1000000010; 352 const ll INF=10000000000000010LL; 353 const int mod=1000000007; 354 const int MAXN=200010, LOG=20; 355 356 ll n, m, k, u, v, x, y, t, a, b, ans; 357 ll A[MAXN]; 358 ll seg[MAXN<<2], lazy[MAXN<<2]; 359 int Mn[MAXN<<2], Mx[MAXN<<2]; 360 361 void Build(int id, int tl, int tr){ 362 if (tr-tl==1){ 363 Mn[id]=Mx[id]=seg[id]=A[tl]; 364 return ; 365 } 366 int mid=(tl+tr)>>1; 367 Build(id<<1, tl, mid); 368 Build(id<<1 | 1, mid, tr); 369 Mn[id]=min(Mn[id<<1], Mn[id<<1 | 1]); 370 Mx[id]=max(Mx[id<<1], Mx[id<<1 | 1]); 371 seg[id]=seg[id<<1] + seg[id<<1 | 1]; 372 } 373 inline void add_lazy(int id, int len, ll val){ 374 Mn[id]=val; 375 Mx[id]=val; 376 lazy[id]=val; 377 seg[id]=len*val; 378 } 379 inline void shift(int id, int tl, int tr){ 380 if (!lazy[id]) return ; 381 int mid=(tl+tr)>>1; 382 add_lazy(id<<1, mid-tl, lazy[id]); 383 add_lazy(id<<1 | 1, tr-mid, lazy[id]); 384 lazy[id]=0; 385 } 386 void Maximize(int id, int tl, int tr, int pos, ll val){ 387 if (pos<=tl || val<=Mn[id]) return ; 388 if (tr<=pos && Mx[id]<=val){ 389 add_lazy(id, tr-tl, val); 390 return ; 391 } 392 shift(id, tl, tr); 393 int mid=(tl+tr)>>1; 394 Maximize(id<<1, tl, mid, pos, val); 395 Maximize(id<<1 | 1, mid, tr, pos, val); 396 Mn[id]=min(Mn[id<<1], Mn[id<<1 | 1]); 397 Mx[id]=max(Mx[id<<1], Mx[id<<1 | 1]); 398 seg[id]=seg[id<<1] + seg[id<<1 | 1]; 399 } 400 int BS1(int id, int tl, int tr, int pos, ll val){ 401 if (tr<=pos || val<Mn[id]) return tr; 402 if (tr-tl==1) return tl; 403 shift(id, tl, tr); 404 int mid=(tl+tr)>>1, tmp=BS1(id<<1, tl, mid, pos, val); 405 if (tmp==mid) return BS1(id<<1 | 1, mid, tr, pos, val); 406 return tmp; 407 } 408 int BS2(int id, int tl, int tr, ll val){ 409 if (seg[id]<=val) return tr; 410 if (tr-tl==1) return tl; 411 shift(id, tl, tr); 412 int mid=(tl+tr)>>1, tmp=BS2(id<<1, tl, mid, val); 413 if (tmp<mid) return tmp; 414 return BS2(id<<1 | 1, mid, tr, val-seg[id<<1]); 415 } 416 ll Get(int id, int tl, int tr, int l, int r){ 417 if (r<=tl || tr<=l) return 0; 418 if (l<=tl && tr<=r) return seg[id]; 419 shift(id, tl, tr); 420 int mid=(tl+tr)>>1; 421 return Get(id<<1, tl, mid, l, r) + Get(id<<1 | 1, mid, tr, l, r); 422 } 423 424 int main(){ 425 ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 426 //freopen("input.txt", "r", stdin); 427 //freopen("output.txt", "w", stdout); 428 cin>>n>>m; 429 for (int i=1; i<=n; i++) cin>>A[i]; 430 Build(1, 1, n+1); 431 while (m--){ 432 cin>>t>>x>>y; 433 if (t==1) Maximize(1, 1, n+1, x+1, y); 434 else{ 435 ans=0; 436 while (1){ 437 x=BS1(1, 1, n+1, x, y); 438 if (x==n+1) break ; 439 ll val=y+Get(1, 1, n+1, 1, x); 440 int xx=BS2(1, 1, n+1, val); 441 // buy [x, xx) 442 ans+=xx-x; 443 y-=Get(1, 1, n+1, x, xx); 444 x=xx; 445 } 446 cout<<ans<<"\n"; 447 } 448 } 449 450 return 0; 451 } 452 ``` 453 454 Tutorial is loading... 455 456 prepared by [Mehrdad_Sohrabi](/profile/Mehrdad_Sohrabi "Grandmaster Mehrdad_Sohrabi") Editorial by [Mehrdad_Sohrabi](/profile/Mehrdad_Sohrabi "Grandmaster Mehrdad_Sohrabi") 457 458 **official solution** 459 460 ``` 461 #include <bits/stdc++.h> 462 #pragma GCC optimize ("O2,unroll-loops") 463 //#pragma GCC optimize("no-stack-protector,fast-math") 464 //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") 465 466 using namespace std; 467 typedef long long ll; 468 typedef long double ld; 469 typedef pair<int, int> pii; 470 typedef pair<pii, int> piii; 471 typedef pair<ll, ll> pll; 472 #define debug(x) cerr<<#x<<'='<<(x)<<endl; 473 #define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl; 474 #define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl; 475 #define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;} 476 #define all(x) x.begin(), x.end() 477 #define pb push_back 478 #define kill(x) return cout<<x<<'\n', 0; 479 480 const ld eps=1e-7; 481 const int inf=1000000010; 482 const ll INF=10000000000000010LL; 483 const int MAXN=505, LOG=20; 484 485 ll n, m, k, u, v, x, y, t, a, b, ans, mod; 486 ll dp1[MAXN], dp2[MAXN]; 487 ll dp3[MAXN][MAXN], dp4[MAXN][MAXN]; 488 ll C[MAXN][MAXN]; 489 490 int main(){ 491 ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 492 //freopen("input.txt", "r", stdin); 493 //freopen("output.txt", "w", stdout); 494 cin>>n>>m>>mod; 495 496 for (int i=0; i<MAXN; i++){ 497 C[i][0]=C[i][i]=1; 498 for (int j=1; j<i; j++) C[i][j]=(C[i-1][j] + C[i-1][j-1])%mod; 499 } 500 dp1[0]=1; 501 for (int n=1; n<MAXN; n++){ 502 for (int i=1; i<=n; i++) dp1[n]=(dp1[n] + dp1[i-1]*dp1[n-i]%mod*C[n-1][i-1])%mod; 503 dp1[n]=(n+1)*dp1[n]%mod; 504 for (int i=1; i<=n; i++){ 505 dp2[n]=(dp2[n] + (n+1)*C[n-1][i-1]%mod*((dp1[i-1]*dp2[n-i] + dp2[i-1]*dp1[n-i])%mod))%mod; 506 dp2[n]=(dp2[n] + C[n-1][i-1]*dp1[i-1]%mod*dp1[n-i]%mod*((i*(i-1)/2+(n-i)*(n-i+1)/2)%mod))%mod; 507 } 508 } 509 510 dp3[0][0]=1; 511 for (int n=1; n<MAXN; n++){ 512 for (int m=0; m<n; m++){ 513 dp3[n][m]=dp3[n-1][m]; 514 dp4[n][m]=dp4[n-1][m]; 515 for (int i=1; i<=m; i++){ 516 dp3[n][m]=(dp3[n][m] + dp3[n-i-1][m-i]*dp1[i]%mod*C[m][i])%mod; 517 dp4[n][m]=(dp4[n][m] + dp3[n-i-1][m-i]*dp2[i]%mod*C[m][i])%mod; 518 dp4[n][m]=(dp4[n][m] + dp4[n-i-1][m-i]*dp1[i]%mod*C[m][i])%mod; 519 } 520 } 521 dp3[n][n]=dp1[n]; 522 dp4[n][n]=dp2[n]; 523 } 524 525 cout<<dp4[n][m]<<"\n"; 526 527 return 0; 528 } 529 ``` 530 531 **O(n2) solution** 532 533 ``` 534 // And you curse yourself for things you never done 535 // Shayan.P 2020-08-29 536 537 #include<bits/stdc++.h> 538 539 #define F first 540 #define S second 541 #define PB push_back 542 #define sz(s) int((s).size()) 543 #define bit(n,k) (((n)>>(k))&1) 544 545 using namespace std; 546 547 typedef long long ll; 548 typedef pair<int,int> pii; 549 550 const int maxn = 510, inf = 1e9 + 10, mod=1e9+7; 551 552 ll n, m; 553 554 ll Pow(ll a, ll b){ 555 b = (b + (mod-1)) % (mod-1); // to handle b == -1 556 int ans=1; 557 for(; b; b>>=1, a=a*a%mod) if (b&1) ans=ans*a%mod; 558 return ans; 559 } 560 inline void add(ll &a, ll b){ 561 a = (a + b) % mod; 562 } 563 564 ll fac[maxn], ifac[maxn]; 565 566 ll C(ll n, ll k){ 567 if (n<k || k<0) return 0; 568 return fac[n]*ifac[k]%mod*ifac[n-k]%mod; 569 } 570 571 int main(){ 572 ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(); 573 574 fac[0] = 1; 575 for(int i = 1; i < maxn; i++) fac[i]=fac[i-1]*i%mod; 576 ifac[maxn-1] = Pow(fac[maxn-1], mod-2); 577 for(int i = maxn-2; i >= 0; i--) ifac[i]=ifac[i+1]*(i+1)%mod; 578 579 cin >> n >> m; 580 ++n; //! 581 582 int ans = 0; 583 for(ll bef = 0; bef < m; bef++){ 584 for(ll w = 1; w + bef < m; w++){ // corner case : bef == 0 585 ll cnt1=Pow(w+1, w-1)*Pow(2, w)%mod; 586 ll cnt2=Pow(n-w-1, bef-1)*Pow(2, bef)%mod*(n-w-1-bef)%mod; 587 ll cnt=cnt1*cnt2%mod*C(w+bef, bef)%mod; 588 ll score=w*(w+1)%mod*n%mod; 589 ll after=Pow(n, m-bef-w-1)*Pow(2, m-bef-w-1) % mod; 590 ans=(ans + cnt*score%mod*after) % mod; 591 } 592 } 593 cout << 1ll * (n-m) * ans % mod * Pow(n, -1) % mod << "\n"; 594 return 0; 595 } 596 ``` 597 598 Tutorial is loading... 599 600 Prepared by [AliShahali1382](/profile/AliShahali1382 "International Grandmaster AliShahali1382") Editorial by [AliShahali1382](/profile/AliShahali1382 "International Grandmaster AliShahali1382") 601 602 **official solution** 603 604 ``` 605 #include <bits/stdc++.h> 606 #pragma GCC optimize ("O2,unroll-loops") 607 //#pragma GCC optimize("no-stack-protector,fast-math") 608 //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") 609 610 using namespace std; 611 typedef long long ll; 612 typedef long double ld; 613 typedef pair<int, int> pii; 614 typedef pair<pii, int> piii; 615 typedef pair<ll, ll> pll; 616 #define debug(x) cerr<<#x<<'='<<(x)<<endl; 617 #define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl; 618 #define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl; 619 #define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;} 620 #define all(x) x.begin(), x.end() 621 #define pb push_back 622 #define kill(x) return cout<<x<<'\n', 0; 623 624 const ld eps=1e-7; 625 const int inf=1000000010; 626 const ll INF=10000000000000010LL; 627 const int mod=1000000007; 628 const int MAXN=400010, LOG=30; 629 630 int n, m, k, u, v, x, y, t, a, b, root, ans; 631 pii A[MAXN], V[MAXN]; 632 int par[MAXN], sum[MAXN]; 633 bool is[MAXN]; 634 vector<int> G[MAXN], grundy; 635 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 636 637 inline int GetH(pii p){ return p.first+p.second;} 638 inline pii GetPar(pii p, int k){ 639 int x=p.first, y=p.second; 640 while (k){ 641 int xx=(x&-x), yy=(y&-y); 642 if (!xx) xx=2*inf; 643 if (!yy) yy=2*inf; 644 int tmp=min(k, min(xx, yy)); 645 k-=tmp; 646 if (xx<yy) x-=tmp; 647 else y-=tmp; 648 } 649 return {x, y}; 650 } 651 inline int Zone(pii p, int n){ 652 if (p.first&(1<<(n-1))) return 2; 653 if (p.second&(1<<(n-1))) return 1; 654 return 0; 655 } 656 void dfs_order(vector<pii> &vec, int n=LOG) { 657 if (n==0 || vec.size()==0) return ; 658 vector<pii> v[3]; 659 for (pii p:vec) { 660 int z=Zone(p, n); 661 p.first&=(1<<(n-1))-1; 662 p.second&=(1<<(n-1))-1; 663 v[z].pb(p); 664 } 665 vec.clear(); 666 for (int i:{0, 1, 2}) dfs_order(v[i], n-1); 667 for (pii p:v[0]) if (!p.first) vec.pb(p); 668 for (pii p:v[1]) vec.pb({p.first, p.second|(1<<(n-1))}); 669 for (pii p:v[0]) if (p.first) vec.pb(p); 670 for (pii p:v[2]) vec.pb({p.first|(1<<(n-1)), p.second}); 671 } 672 pii Lca(pii u, pii v, int n=LOG) { 673 if (n==0) return {0, 0}; 674 int zu = Zone(u, n), zv = Zone(v, n); 675 if (zu > zv) swap(u, v), swap(zu, zv); 676 u.first&=(1<<(n-1))-1; 677 u.second&=(1<<(n-1))-1; 678 v.first&=(1<<(n-1))-1; 679 v.second&=(1<<(n-1))-1; 680 if (zu == 1 && zv == 2) return {0, 0}; 681 if (zu == 2 && zv == 2){ 682 pii A = Lca(u, v, n-1); 683 return {A.first+(1<<(n-1)), A.second}; 684 } 685 if (zu == 1 && zv == 1) { 686 pii A = Lca(u, v, n-1); 687 return {A.first, A.second+(1<<(n-1))}; 688 } 689 if (zv == 1) return Lca(u, {0, (1<<(n-1))-1}, n-1); 690 if (zv == 2) return Lca(u, {(1<<(n-1))-1, 0}, n-1); 691 return Lca(u, v, n-1); 692 } 693 inline int GetId(pii p){ 694 return lower_bound(V, V+n, p)-V; 695 } 696 inline bool IsPar(pii u, pii v){ 697 if (GetH(u)>GetH(v)) return 0; 698 return GetPar(v, GetH(v)-GetH(u))==u; 699 } 700 int dfs(int node){ 701 for (int v:G[node]) sum[node]+=dfs(v); 702 return sum[node]; 703 } 704 705 int main(){ 706 ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 707 //freopen("input.txt", "r", stdin); 708 //freopen("output.txt", "w", stdout); 709 vector<pii> vec; 710 cin>>m; 711 for (int i=0; i<2*m; i++) cin>>A[i].first>>A[i].second, vec.pb(A[i]); 712 sort(all(vec)); 713 vec.resize(unique(all(vec))-vec.begin()); 714 dfs_order(vec); 715 for (int i=vec.size()-1; i; i--) vec.pb(Lca(vec[i], vec[i-1])); 716 sort(all(vec)); 717 vec.resize(unique(all(vec))-vec.begin()); 718 dfs_order(vec); 719 n=vec.size(); 720 721 debug("sorted") 722 723 for (int i=0; i<n; i++) V[i]=vec[i]; 724 sort(V, V+n); 725 vector<int> stk={root=GetId(vec[0])}; 726 for (int i=1; i<n; i++){ 727 int v=GetId(vec[i]); 728 while (!IsPar(V[stk.back()], V[v])) stk.pop_back(); 729 par[v]=stk.back(); 730 G[stk.back()].pb(v); 731 stk.pb(v); 732 } 733 734 for (int i=0; i<2*m; i+=2){ 735 int u=GetId(A[i]), v=GetId(A[i+1]), lca=GetId(Lca(A[i], A[i+1])); 736 sum[u]++; 737 sum[v]++; 738 sum[lca]-=2; 739 is[lca]=1; 740 } 741 dfs(root); 742 for (int v=0; v<n; v++){ 743 if (sum[v]){ 744 grundy.pb(GetH(V[par[v]])+1); 745 grundy.pb(GetH(V[v])+1); 746 } 747 else if (is[v]){ 748 grundy.pb(GetH(V[v])); 749 grundy.pb(GetH(V[v])+1); 750 } 751 } 752 sort(all(grundy)); 753 vec.clear(); 754 int last=-1; 755 for (int x:grundy){ 756 if (last==-1){ 757 if (vec.empty() || vec.back().second<x) last=x; 758 else{ 759 last=vec.back().first; 760 vec.pop_back(); 761 } 762 } 763 else{ 764 if (last<x) vec.pb({last, x}); 765 last=-1; 766 } 767 } 768 ans=2*vec.size(); 769 if (ans && vec[0].first==0) ans--; 770 cout<<ans<<"\n"; 771 772 return 0; 773 } 774 ```