Submission #911205

#TimeUsernameProblemLanguageResultExecution timeMemory
911205cadmiumskyFish 2 (JOI22_fish2)C++17
0 / 100
1331 ms1048576 KiB
#include <bits/stdc++.h> #define all(x) (x).begin(),(x).end() using namespace std; using ll = long long; using ld = long double; //#define int ll #define sz(x) ((int)(x).size()) using pii = pair<int,int>; using tii = tuple<int,int,int>; const int nmax = 1e5 + 5; const int inf = 1e9 + 5; template<typename Node> struct AINT { vector<Node> aint; int n; void init(int _n, Node TMP = Node()) { n = _n; aint.assign(2 * n + 5, TMP); } tii getsons(int node, int cl, int cr) { int mid = cl + cr >> 1; return tii{mid, node + 1, node + (mid - cl + 1) * 2};} template<class CB> void walk(int ismutable, int toRight, CB&& cb) { if(ismutable == 0 && toRight == 0) walk<0, 0>(cb, 1, 1, n); else if(ismutable == 0) walk<0, 1>(cb, 1, 1, n); else if(toRight == 0) walk<1, 0>(cb, 1, 1, n); else walk<1, 1>(cb, 1, 1, n); } template<int ismutable, int toRight, class CB> void walk(CB&& cb, int node, int cl, int cr) { //cerr << node << '\t' << cl << ' ' << cr << '\n'; if(!cb(aint[node], cl, cr)) return; auto [mid, L, R] = getsons(node, cl, cr); aint[node].push(aint[L], aint[R]); if(toRight) walk<ismutable, toRight>(cb, L, cl, mid), walk<ismutable, toRight>(cb, R, mid + 1, cr); else walk<ismutable, toRight>(cb, R, mid + 1, cr), walk<ismutable, toRight>(cb, L, cl, mid); if(ismutable) aint[node].pull(aint[L], aint[R]); return; } }; struct MinCounter { int mn, cnt; int add; MinCounter(int a, int b, int c = 0): mn(a), cnt(b), add(c) {;} MinCounter(): mn(inf), cnt(0), add(0) {;} void push(MinCounter& a, MinCounter& b) { a.mn += add; a.add += add; b.add += add; b.mn += add; add = 0; } void pull(const MinCounter a, const MinCounter b) { *this = MinCounter(min(a.mn, b.mn), a.cnt * (a.mn <= b.mn) + b.cnt * (b.mn <= a.mn)); } }; struct GreaterFinder { int mx; GreaterFinder(int a = 0): mx(a) {;} void pull(const GreaterFinder& a, const GreaterFinder& b) { *this = GreaterFinder(max(a.mx, b.mx)); } void push(const GreaterFinder& a, const GreaterFinder& b) {;} }; struct Sum { ll sum; Sum(ll a = 0): sum(a) {;} void pull(const Sum& a, const Sum& b) { *this = Sum(a.sum + b.sum); } void push(const Sum& a, const Sum& b) {;} }; int a[nmax]; AINT<Sum> sum; ll getsum(int l, int r) { ll rez = 0; for(int i = l; i <= r; i++) rez += a[i]; //sum.walk(0, 1, [&](Sum& a, int cl, int cr) { if(cr < l || r < cl) return 0; if(l <= cl && cr <= r) { rez += a.sum; return 0; } return 1; }); return rez; return rez; } AINT<MinCounter> mncnt; int n; namespace Finders { AINT<GreaterFinder> finder; int nextGreater(int P, int lim) { // urmatorul de la pozitia P >= lim for(int i = P; i <= n; i++) if(a[i] >= lim) return i; return n + 1; int rez = n + 1; finder.walk(0, 1, [&](GreaterFinder& a, int cl, int cr) { if(rez < cl) return 0; if(cr < P || a.mx < lim) { rez = cr + 1; return 0; } if(cl == cr) { rez = cl; return 0; } return 1; }); return rez; } int prevGreater(int P, int lim) { for(int i = P; i > 0; i--) if(a[i] >= lim) return i; return 0; int rez = 0; finder.walk(0, 0, [&](GreaterFinder& a, int cl, int cr) { if(rez > cr) return 0; if(P < cl || a.mx < lim) { rez = cl - 1; return 0; } if(cl == cr) { rez = cl; return 0; } return 1; }); return rez; } int nextBreaker(int L, int start) { int ptr = start; while(ptr < n) { if(getsum(L, ptr) < a[ptr + 1]) { return ptr + 1; } ptr = nextGreater(ptr + 1, a[ptr + 1] * 2) - 1; } return n + 1; } int prevBreaker(int R, int start) { int ptr = start; while(ptr > 1) { if(getsum(ptr, R) < a[ptr - 1]) { return ptr - 1; } ptr = prevGreater(ptr - 1, a[ptr - 1] * 2) + 1; } return 0; } } vector<pii> getIntervs(int P) { //cerr << "lmao\n"; using namespace Finders; vector<pii> elems; int L = P, R = P, direction = 1, fail = 0; while(L > 1 || R < n) { if(direction == 1) { int nvR = nextBreaker(L, R) - 1; //cerr << nvR << '\n'; if(nvR == R && fail) { elems.emplace_back(L, R); if(a[L] <= a[R] || R == n) L--; else R++; fail = 0; } else { fail = R == nvR; R = nvR; } } else { int nvL = prevBreaker(R, L) + 1; //cerr << nvL << '\n'; if(nvL == L && fail) { elems.emplace_back(L, R); if(a[L] <= a[R] || R == n) L--; else R++; fail = 0; } else {fail = L == nvL; L = nvL; } } direction *= -1; } //cerr << "---\ncu vectorul:\n"; //for(int i = 1; i <= n; i++) cerr << a[i] << ' '; cerr << '\n'; //cerr << P << " apartine urmatoarelor segmente:\n"; //for(auto [l, r] : elems) //cerr << l << ", " << r << '\n'; //cerr << "----\n"; //cerr << "----\n"; return elems; } namespace Segments { set<pii> appearingIntervs; void erase(int l, int r) { if(appearingIntervs.count(pii{l, r})) { appearingIntervs.erase(pii{l, r}); mncnt.walk(1, 1, [&](MinCounter& val, int cl, int cr) { if(cr < l || r < cl) return 0; if(l <= cl && cr <= r) { val.mn -= 1; val.add -= 1; return 0; } return 1; }); } return; } void insert(int l, int r) { if(!appearingIntervs.count(pii{l, r})) { appearingIntervs.insert(pii{l, r}); mncnt.walk(1, 1, [&](MinCounter& val, int cl, int cr) { if(cr < l || r < cl) return 0; if(l <= cl && cr <= r) { val.mn += 1; val.add += 1; return 0; } return 1; }); } return; } } void updPoz(int P, int x) { vector<pii> V = getIntervs(P), T; if(P > 1) T = getIntervs(P - 1), copy(all(T), back_inserter(V)); if(P < n) T = getIntervs(P + 1), copy(all(T), back_inserter(V)); for(auto [l, r] : V) Segments::erase(l, r); Finders::finder.walk(1, 1, [&](GreaterFinder& val, int cl, int cr) { if(cr < P || P < cl) return 0; if(cl == cr) { val = GreaterFinder(x); return 0; } return 1; }); a[P] = x; sum.walk(1, 1, [&](Sum& val, int cl, int cr) { if(cr < P || P < cl) return 0; if(cl == cr) { val = Sum(x); return 0; } return 1; }); V = getIntervs(P); if(P > 1) T = getIntervs(P - 1), copy(all(T), back_inserter(V)); if(P < n) T = getIntervs(P + 1), copy(all(T), back_inserter(V)); for(auto [l, r] : V) Segments::insert(l, r); return; } int query(int l, int r) { int answer = l, ptr = l; while(ptr <= r) { ptr = Finders::nextBreaker(l, ptr); if(ptr <= r) answer = ptr; ptr = Finders::nextGreater(ptr, a[ptr] + 1); } l = answer; answer = ptr = r; while(ptr >= l) { ptr = Finders::prevBreaker(r, ptr); if(ptr >= l) answer = ptr; ptr = Finders::prevGreater(ptr, a[ptr] + 1); } r = answer; MinCounter cnt(1e9 + 5, -1, 0); mncnt.walk(0, 1, [&](MinCounter& val, int cl, int cr) { if(cr < l || r < cl) return 0; if(l <= cl && cr <= r) { cnt.pull(cnt, val); return 0; } return 1; }); return cnt.cnt; } signed main() { cin >> n; for(int i = 1; i <= n; i++) { cin >> a[i]; } using namespace Finders; finder.init(n); mncnt.init(n); sum.init(n); //cerr << "initializam si noi?.."; finder.walk(1, 1, [&](GreaterFinder& val, int cl, int cr) { if(cl != cr) return 1; val = GreaterFinder(a[cl]); return 0;}); mncnt.walk(1, 1, [&](MinCounter& val, int cl, int cr) { if(cl != cr) return 1; val = MinCounter(0, 1); return 0;}); sum.walk(1, 1, [&](Sum& val, int cl, int cr) { if(cl != cr) return 1; val = Sum(a[cl]); return 0;}); //cerr << "sau hmphhphph\n"; vector<pii> V, T; for(int i = 1; i <= n; i++) { T = getIntervs(i); copy(all(T), back_inserter(V)); } //cerr << "Ai fi crezut ca dupa 89 ne-am fi potolit\n"; for(auto [l, r] : V) { Segments::insert(l, r); } //cerr << "Mai bine de atat\n"; int q; cin >> q; for(int TC = 0, t, x, y; TC < q; TC++) { //cerr << "o data\n"; cin >> t >> x >> y; if(t == 1) updPoz(x, y); else cout << query(x, y) << '\n'; //cerr << "de doua ori data\n\n"; } } /** Anul asta se da centroid. -- Surse oficiale */

Compilation message (stderr)

fish2.cpp: In instantiation of 'tii AINT<Node>::getsons(int, int, int) [with Node = GreaterFinder; tii = std::tuple<int, int, int>]':
fish2.cpp:40:24:   required from 'void AINT<Node>::walk(CB&&, int, int, int) [with int ismutable = 0; int toRight = 0; CB = Finders::nextGreater(int, int)::<lambda(GreaterFinder&, int, int)>&; Node = GreaterFinder]'
fish2.cpp:29:50:   required from 'void AINT<Node>::walk(int, int, CB&&) [with CB = Finders::nextGreater(int, int)::<lambda(GreaterFinder&, int, int)>; Node = GreaterFinder]'
fish2.cpp:118:171:   required from here
fish2.cpp:26:56: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |   tii getsons(int node, int cl, int cr) { int mid = cl + cr >> 1; return tii{mid, node + 1, node + (mid - cl + 1) * 2};}
      |                                                     ~~~^~~~
fish2.cpp: In instantiation of 'tii AINT<Node>::getsons(int, int, int) [with Node = MinCounter; tii = std::tuple<int, int, int>]':
fish2.cpp:40:24:   required from 'void AINT<Node>::walk(CB&&, int, int, int) [with int ismutable = 0; int toRight = 0; CB = Segments::erase(int, int)::<lambda(MinCounter&, int, int)>&; Node = MinCounter]'
fish2.cpp:29:50:   required from 'void AINT<Node>::walk(int, int, CB&&) [with CB = Segments::erase(int, int)::<lambda(MinCounter&, int, int)>; Node = MinCounter]'
fish2.cpp:222:8:   required from here
fish2.cpp:26:56: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
fish2.cpp: In instantiation of 'tii AINT<Node>::getsons(int, int, int) [with Node = Sum; tii = std::tuple<int, int, int>]':
fish2.cpp:40:24:   required from 'void AINT<Node>::walk(CB&&, int, int, int) [with int ismutable = 0; int toRight = 0; CB = updPoz(int, int)::<lambda(Sum&, int, int)>&; Node = Sum]'
fish2.cpp:29:50:   required from 'void AINT<Node>::walk(int, int, CB&&) [with CB = updPoz(int, int)::<lambda(Sum&, int, int)>; Node = Sum]'
fish2.cpp:271:4:   required from here
fish2.cpp:26:56: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
#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...