Submission #1265928

#TimeUsernameProblemLanguageResultExecution timeMemory
1265928canhnam357Nekameleoni (COCI15_nekameleoni)C++20
140 / 140
1336 ms68636 KiB
// source problem : #include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() #define int long long #define MASK(i) (1LL << (i)) void ckmax(int& f, int s) { f = (f > s ? f : s); } void ckmin(int& f, int s) { f = (f < s ? f : s); } int k; const int inf = 1e18; struct info { vector<int> pre, suf, p, s; int ans; info() { ans = 0; } info(int val, int pos) { p.push_back(pos); s.push_back(pos); pre.push_back(val); suf.push_back(val); ans = (k == 1 ? 1 : inf); } }; info operator+(info a, info b) { if (!a.ans) return b; if (!b.ans) return a; info res; res.ans = min(a.ans, b.ans); res.pre = a.pre; res.p = a.p; for (int i = 0; i < b.pre.size(); i++) { int x = b.pre[i] | res.pre.back(); if (x != res.pre.back()) { res.pre.push_back(x); res.p.push_back(b.p[i]); } } res.suf = b.suf; res.s = b.s; for (int i = 0; i < a.suf.size(); i++) { int x = a.suf[i] | res.suf.back(); if (x != res.suf.back()) { res.suf.push_back(x); res.s.push_back(a.s[i]); } } int i = a.suf.size() - 1; for (int j = 0; j < b.pre.size(); j++) { while (i >= 0 && (b.pre[j] | a.suf[i]) == MASK(k) - 1) i--; if (i != a.suf.size() - 1) { ckmin(res.ans, b.p[j] - a.s[i + 1] + 1); } } return res; } vector<int> a; info st[1 << 18]; void build(int id = 1, int l = 1, int r = 1 << 17) { if (l == r) { if (l <= a.size()) st[id] = info(MASK(a[l - 1]), l); return; } int mid = (l + r) >> 1; build(id << 1, l, mid); build(id << 1 | 1, mid + 1, r); st[id] = st[id << 1] + st[id << 1 | 1]; } void update(int pos, int val, int id = 1, int l = 1, int r = 1 << 17) { if (pos < l || pos > r) return; if (l == r) { st[id] = info(val, pos); return; } int mid = (l + r) >> 1; update(pos, val, id << 1, l, mid); update(pos, val, id << 1 | 1, mid + 1, r); st[id] = st[id << 1] + st[id << 1 | 1]; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, q; cin >> n >> k >> q; a.resize(n); for (int &i : a) cin >> i, i--; build(); while (q--) { int t; cin >> t; if (t == 2) { int x = st[1].ans; cout << (x > n ? -1LL : x) << '\n'; } else { int p, x; cin >> p >> x; x--; update(p, MASK(x)); } } 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...
#Verdict Execution timeMemoryGrader output
Fetching results...