結果
問題 | No.2935 Division Into 3 (Mex Edition) |
ユーザー |
👑 ![]() |
提出日時 | 2024-10-29 21:32:49 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 448 ms / 5,000 ms |
コード長 | 5,131 bytes |
コンパイル時間 | 1,300 ms |
コンパイル使用メモリ | 93,380 KB |
実行使用メモリ | 78,900 KB |
最終ジャッジ日時 | 2024-10-29 21:33:02 |
合計ジャッジ時間 | 11,908 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,816 KB |
testcase_02 | AC | 2 ms
6,820 KB |
testcase_03 | AC | 250 ms
56,596 KB |
testcase_04 | AC | 322 ms
76,300 KB |
testcase_05 | AC | 345 ms
78,832 KB |
testcase_06 | AC | 376 ms
78,704 KB |
testcase_07 | AC | 272 ms
67,456 KB |
testcase_08 | AC | 280 ms
70,232 KB |
testcase_09 | AC | 299 ms
78,728 KB |
testcase_10 | AC | 340 ms
78,804 KB |
testcase_11 | AC | 218 ms
68,176 KB |
testcase_12 | AC | 229 ms
57,260 KB |
testcase_13 | AC | 377 ms
78,848 KB |
testcase_14 | AC | 356 ms
78,704 KB |
testcase_15 | AC | 304 ms
60,996 KB |
testcase_16 | AC | 191 ms
40,164 KB |
testcase_17 | AC | 367 ms
78,892 KB |
testcase_18 | AC | 377 ms
78,712 KB |
testcase_19 | AC | 344 ms
70,548 KB |
testcase_20 | AC | 405 ms
78,900 KB |
testcase_21 | AC | 344 ms
76,876 KB |
testcase_22 | AC | 419 ms
78,808 KB |
testcase_23 | AC | 448 ms
78,848 KB |
ソースコード
#include <iostream> #include <string> #include <vector> #include <algorithm> using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(int i=0; i<int(n); i++) const i64 INF = 1001001001001001001; template<typename A> void chmin(A& l, const A& r){ if(r < l) l = r; } template<typename A> void chmax(A& l, const A& r){ if(l < r) l = r; } #include <atcoder/modint> using Modint = atcoder::static_modint<998244353>; using namespace std; #include <array> namespace nachia { template< class S, S(*op)(S a, S b) > struct PersistentSegtree { struct Node { int l, r; S v; }; int xN; int N, logN; S me; vector<Node> V; void merge(int p){ V[p].v = op(V[V[p].l].v, V[V[p].r].v); } PersistentSegtree() {} PersistentSegtree(int z, S e) : xN(z), N(1), logN(0), me(e) { while(N < z){ N *= 2; logN++; } V.assign(N*2-1, { -1,-1,me }); for(int i=N-2; i>=0; i--){ V[i].l = i*2+1; V[i].r = i*2+2; } } PersistentSegtree(const vector<S>& v, S e) : PersistentSegtree(v.size(), e) { for(int i=0; i<int(v.size()); i++) V[N-1+i].v = v[i]; for(int i=N-2; i>=0; i--) merge(i); } int copy_node(int p){ V.push_back(V[p]); return V.size() - 1; } int set(int t, int p, S v){ vector<int> P; P.push_back(copy_node((t == -1) ? 0 : t)); for(int d=logN-1; d>=0; d--){ int pp = P.back(); if(p & (1<<d)){ P.push_back(copy_node(V[pp].r)); V[pp].r = P.back(); } else { P.push_back(copy_node(V[pp].l)); V[pp].l = P.back(); } pp = P.back(); } V[P.back()].v = v; for(int i=(int)P.size()-2; i>=0; i--) merge(P[i]); return P.front(); } int where(int t, int p){ int s = (t == -1) ? 0 : t; for(int d=logN-1; d>=0; d--) s = ((p & (1<<d)) ? V[s].r : V[s].l); return s; } S get(int t, int p){ int s = (t == -1) ? 0 : t; for(int d=logN-1; d>=0; d--) s = ((p & (1<<d)) ? V[s].r : V[s].l); return V[s].v; } S prod(int t, int l, int r){ struct DFSV { int l, r, i; }; vector<DFSV> G; G.reserve(logN*2+2); int s = (t == -1) ? 0 : t; G.push_back({ 0,N,s }); S res = me; while(G.size()){ DFSV g = G.back(); G.pop_back(); int a = g.l, b = g.r, i = g.i; if(r <= a || b <= l) continue; if(l <= a && b <= r){ res = op(res, V[i].v); continue; } G.push_back({ (a+b)/2, b, V[i].r }); G.push_back({ a, (a+b)/2, V[i].l }); } return res; } private: template<class E> int minLeft2(int r, E cmp, int i, int a = 0, int b = 0) const { static S x; if(b == 0){ a=0; b=N; x=me; } if(r <= a) return a; if(b <= r){ S nx = op(V[i].v, x); if(cmp(nx)){ x = nx; return a; } } if(b-a == 1) return b; int q = minLeft2(r, cmp, V[i].r, (a+b)/2, b); if(q > (a+b)/2) return q; return minLeft2(r, cmp, V[i].l, a, (a+b)/2); } template<class E> int maxRight2(int l, E cmp, int i, int a = 0, int b = 0) const { static S x; if(b == 0){ a=0; b=N; x=me; } if(b <= l) return b; if(l <= a){ S nx = op(x, V[i].v); if(cmp(nx)){ x = nx; return b; } } if(b-a == 1) return a; int q = maxRight2(l, cmp, V[i].l, a, (a+b)/2); if(q < (a+b)/2) return q; return maxRight2(l, cmp, V[i].r, (a+b)/2, b); } public: // bool cmp(S) template<class E> int minLeft(int t, int r, E cmp) const { int s = (t == -1) ? 0 : t; return minLeft2(r, cmp, s); } // bool cmp(S) template<class E> int maxRight(int t, int l, E cmp) const { int s = (t == -1) ? 0 : t; int x = maxRight2(l, cmp, s); return x > xN ? xN : x; } }; } int maxop(int l, int r){ return max(l,r); } void testcase(){ int N; cin >> N; vector<int> A(N); rep(i,N) cin >> A[i]; using Ds = nachia::PersistentSegtree<int, maxop>; vector<Ds> ds; rep(t,3) ds.emplace_back(vector<int>(N+1, N+1), -1); vector<array<int,3>> T(N); { vector<array<int,3>> B(N); rep(i,N) B[i].fill(N+1); array<int,3> t; t.fill(-1); for(int i=N-1; i>=0; i--){ if(A[i] < N){ auto& b = B[A[i]]; b[2] = b[1]; b[1] = b[0]; b[0] = i+1; rep(s,3) t[s] = ds[s].set(t[s], A[i], b[s]); } T[i] = t; } } int Q; cin >> Q; int ans = 0; rep(qi,Q){ int a,b; cin >> a >> b; int l = a ^ ans; int r = b ^ ans; l--; int C[3] = {}; rep(s,3) C[s] = ds[s].maxRight(T[l][s], 0, [r](int x){ return x <= r; }); ans = C[0] + C[1] + C[2]; rep(s,3) if(C[s] == 0) chmin(ans, r-l-3+s); cout << ans << '\n'; } } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); testcase(); return 0; }