Submission #1108979

#TimeUsernameProblemLanguageResultExecution timeMemory
1108979KerimMosaic (IOI24_mosaic)C++17
48 / 100
703 ms100284 KiB
#include "bits/stdc++.h" #define ll long long #define pb push_back #define pii pair<int, int> using namespace std; const int N = 4e5+5; int cnt[N], arcalyk[4][N]; int wow(int a, int b){ return (!(a|b)?1:0); } vector<ll> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R){ int n = (int)X.size(); assert(X.front()==Y.front()); map<pii, int> mp; for(int i = 1; i <= n; ++i) mp[{1, i}] = X[i-1], mp[{i, 1}] = Y[i-1]; for(int i = 2; i <= n; ++i) for(int j = 2; j <= 3; ++j) mp[{i, j}] = wow(mp[{i-1, j}], mp[{i, j-1}]); for(int i = 2; i <= 3; ++i) for(int j = 2; j <= n; ++j) mp[{i, j}] = wow(mp[{i-1, j}], mp[{i, j-1}]); // int ii = 3; // for(int jj = 3; jj <= n; ++jj) // cnt[ii-jj+n] = mp[{ii, jj}]; for (auto [key, value]: mp) cnt[key.first-key.second+n] = value; for (int i = 1; i <= 3; i++) for (int j = 1; j <= n; j++) arcalyk[i][j] = mp[{i,j}] + arcalyk[i][j-1]; for (int i = 1; i < n+n; i++) cnt[i] += cnt[i-1]; vector<ll> ans; for(int i = 0; i < (int)L.size(); ++i){ assert(T[i] == B[i]); int x = T[i]+1, y = L[i]+1, yy = R[i]+1; if (x <= 3){ ans.pb(arcalyk[x][yy]-arcalyk[x][y-1]); continue; } int res = 0; while (y <= 3 and y <= yy) res += mp[{x, y}], y += 1; if (y <= yy){ int a = x-y+n, b = x-yy+n; assert(b <= a); res += cnt[a] - cnt[b-1]; } ans.pb(res); } return ans; } // int main(){ // int n; // scanf("%d", &n); // vector<int> X, Y; // for(int i = 1; i <= n; ++i){ // int x; // scanf("%d", &x); // X.pb(x); // } // for(int i = 1; i <= n; ++i){ // int x; // scanf("%d", &x); // Y.pb(x); // } // int q; // scanf("%d", &q); // vector<int> T, B, L, R; // while(q--){ // int a, b, c, d; // scanf("%d%d%d%d", &a, &b, &c, &d); // T.pb(a), B.pb(b), L.pb(c), R.pb(d); // } // vector<ll> ans = mosaic(X, Y, T, B, L, R); // for(ll i : ans) // printf("%lld ", i); // puts(""); // 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...