Submission #1238477

#TimeUsernameProblemLanguageResultExecution timeMemory
1238477banganMosaic (IOI24_mosaic)C++20
100 / 100
138 ms24612 KiB
#include "mosaic.h" #include <bits/stdc++.h> #include <vector> using namespace std; #define ll long long #define sep ' ' #define pb push_back std::vector<long long> mosaic(std::vector<int> X, std::vector<int> Y, std::vector<int> T, std::vector<int> B, std::vector<int> lo, std::vector<int> hi) { int n = X.size(); int q = (int)T.size(); if (n==1) return vector<ll> (q, X[0]); vector<ll> ans(q, 0); vector<int> all(q); iota(all.begin(), all.end(), 0); sort(all.begin(), all.end(), [&](int i, int j) { return B[i]<B[j]; }); auto it = all.begin(); while (it!=all.end() && B[*it] < 2) it++; vector<ll> a; for (int i=1; i<n; i++) a.pb(X[i]); for (int i = n-3; 0<=i; i--) a[i] += a[i+1]; auto get = [&](int l, int r) { if (r+1 == a.size()) return a[l]; return a[l] - a[r+1]; }; { vector<ll> y; for (int t : Y) y.pb(t); for (int i=1; i<y.size(); i++) y[i] += y[i-1]; for (int i=0; i<q; i++) if (lo[i]==0) { ans[i] += y[B[i]]; if (0 <= T[i]-1) ans[i] -= y[T[i]-1]; lo[i]++; } } for (int r=0; r<2; r++) { for (int i=0; i<q; i++) { if (r==T[i] && T[i]<=B[i] && lo[i]<=hi[i]) { T[i]++; int L = lo[i]; int R = hi[i]; L--, R--; ans[i] += get(L, R); } } if (r+1 != n) { vector<ll> b; b.pb((Y[r+1]|get(0, 0))^1); for (int i=1; i<a.size(); i++) b.pb((b.back()|get(i, i))^1); swap(a, b); for (int i = n-3; 0<=i; i--) a[i] += a[i+1]; } } // return ans; { vector<ll> b = a; a.clear(); a.shrink_to_fit(); for (int i=0; i<n; i++) a.pb(0); for (ll i:b) a.pb(i); } vector<ll> b; { vector<ll> t = a; reverse(t.begin(), t.end()); for (int i=0; i<n; i++) t.pop_back(); reverse(t.begin(), t.end()); for (int i = n-3; 0<=i; i--) t[i] += t[i+1]; for (int i=0; i<n; i++) b.pb(0); for (ll i:t) b.pb(i); } int z=n; vector<ll> pre = {get(z, z)}; auto get_one = [&](int i, int c) -> ll { int l = i; int r = i+c; assert(a.size()==b.size()); if (b.size() <= l) return 0; if (b.size() <= r) return b[l]; return b[l]-b[r]; }; auto GET = [&](int l, int r, int c) -> ll { assert(a.size()==b.size()); return get_one(l, c) - get_one(r+1, c); }; for (int r=2; r<n; r++) { while (it!=all.end() && B[*it]==r) { int L = lo[*it]; int R = hi[*it]; int U = T[*it]; int D = B[*it]; if (R<L || D<U) { it++; continue; } assert(1<=L && 2<=U); L--; R--; if (L==0) { ans[*it] += pre.back(); if (0 <= U-3) ans[*it] -= pre[U-3]; L++; } if (L<=R) ans[*it] += GET(z+L, z+R, D-U+1); it++; } if (r+1 != n) { z--; int t = (Y[r+1]|get(z+1, z+1))^1; if (z+2 < a.size()) { a[z+1] = ((get(z+2, z+2)|t) ^ 1) + a[z+2]; b[z+1] = a[z+1] + b[z+2]; } a[z] = t + a[z+1]; b[z] = a[z] + b[z+1]; pre.pb(pre.back() + get(z, z)); } } return ans; }
#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...