제출 #1190662

#제출 시각아이디문제언어결과실행 시간메모리
1190662epicci23Mosaic (IOI24_mosaic)C++20
100 / 100
541 ms92176 KiB
#include "bits/stdc++.h" //#include "mosaic.h" #define ll long long #define all(v) v.begin() , v.end() #define sz(a) (ll)a.size() using namespace std; const ll N = 2e5 + 5; ll n, q; ll ans[N], row[N], col[N]; ll ar[N][6], v[6][N], dp_ar[N][6], dp_v[6][N]; vector<array<ll,4>> to_calc; vector<array<ll,3>> ones; vector<ll> prer,prec; vector<ll> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R) { n = sz(X); for(int i = 1; i <= n; i++) col[i] = X[i-1]; for(int i = 1; i <= n; i++) row[i] = Y[i-1]; for(int i = 1; i <= n; i++){ for(int j = 1; j <= 5; j++){ if(i == 1) ar[i][j] = col[j]; else if(j == 1) ar[i][j] = row[i]; else ar[i][j] = min(1 - ar[i-1][j], 1 - ar[i][j-1]); dp_ar[i][j] = dp_ar[i-1][j] + dp_ar[i][j-1] - dp_ar[i-1][j-1] + (ar[i][j] == 1); } } for(int i = 1; i <= 5; i++){ for(int j = 1; j <= n; j++){ if(i == 1) v[i][j] = col[j]; else if(j == 1) v[i][j] = row[i]; else v[i][j] = min(1 - v[i-1][j], 1 - v[i][j-1]); dp_v[i][j] = dp_v[i-1][j] + dp_v[i][j-1] - dp_v[i-1][j-1] + (v[i][j] == 1); } } for(int j = n; j > 5; j--){ if(v[5][j] == 1){ ones.push_back({5 - j, 5, j}); } } for(int i = 5; i <= n; i++){ if(ar[i][5] == 1){ ones.push_back({i - 5, i, 5}); } } prer.assign(sz(ones) + 2, 0), prec.assign(sz(ones) + 2, 0); for(int i = 0; i < sz(ones); i++){ prer[i] = (i > 0 ? prer[i-1] : 0) + ones[i][1]; prec[i] = (i > 0 ? prec[i-1] : 0) + ones[i][2]; } q = sz(B); for(int i=0;i<q;i++){ int t = T[i] + 1, b = B[i] + 1, l = L[i] + 1, r = R[i] + 1; to_calc.push_back({b, r, i, 1}); to_calc.push_back({b, l - 1, i, -1}); to_calc.push_back({t - 1, r, i, -1}); to_calc.push_back({t - 1, l - 1, i, 1}); } for(array<ll,4> X : to_calc){ if(X[0] == 0 || X[1] == 0) continue; if(X[0] >= 5 && X[1] >= 5){ ll res = dp_v[4][X[1]] + dp_ar[X[0]][4] - dp_v[4][4]; //cout << X[0] << ' ' << X[1] <<' ' << res << '\n'; ll l = lower_bound(all(ones), array<ll,3>{5 - X[1], 5, X[1]}) - ones.begin(); ll r = upper_bound(all(ones), array<ll,3>{X[0] - 5, X[0], 5}) - ones.begin(); r--; //cout << l << ' ' << r << '\n'; if(l <= r){ int gl = l, gr = r; while(gl < gr){ int mid = (gl + gr + 1) / 2; if(X[1] - ones[mid][2] <= X[0] - ones[mid][1]) gl = mid; else gr = mid - 1; } while(gl >= 0 && X[1] - ones[gl][2] > X[0] - ones[gl][1]) gl--; //cout << "gl : " << gl << '\n'; if(gl >= l){ res += (gl - l + 1) * (X[1] + 1) - (prec[gl] - (l == 0 ? 0 : prec[l - 1])); } //cout << X[0] << ' ' << X[1] <<' ' << res << '\n'; //while(gl < sz(ones) && X[1] - ones[gl][2] < X[0] - ones[gl][1]) gl++; //cout << "gl : " << gl << '\n'; if(gl + 1 <= r){ res += (r - gl) * (X[0] + 1) - (prer[r] - (gl >= 0 ? prer[gl] : 0)); } //cout << X[0] << ' ' << X[1] <<' ' << res << '\n'; } //for(int u = l; u <= r; u++) res += min(X[0] - ones[u][1] + 1, X[1] - ones[u][2] + 1); // opt here! // cout << X[0] << ' ' << X[1] <<' ' << res << '\n'; ans[X[2]] += X[3] * res; } else{ if(X[0] < 5){ ans[X[2]] += X[3] * dp_v[X[0]][X[1]]; } else{ ans[X[2]] += X[3] * dp_ar[X[0]][X[1]]; } } } vector<ll> res(q); for(int i=0;i<q;i++) res[i] = ans[i]; return res; } /*void _(){ int _n, _q; cin >> _n; vector<int> xd1(_n, 0), xd2(_n, 0); for(int i = 0; i < _n; i++) cin >> xd1[i]; for(int i = 0; i < _n; i++) cin >> xd2[i]; cin >> _q; vector<int> T(_q),B(_q),L(_q),R(_q); for(int i=0;i<_q;i++){ cin >> T[i] >> B[i] >> L[i] >> R[i]; } vector<long long> res = mosaic(xd1,xd2,T,B,L,R); for(int i = 0; i < sz(res); i++) cout << res[i] << '\n'; } int32_t main(){ ios::sync_with_stdio(0); cin.tie(0); int tc=1;//cin >> tc; while(tc--) _(); return 0; }*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...