| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 911237 |
2024-01-18T16:43:08 Z |
cadmiumsky |
Fish 2 (JOI22_fish2) |
C++17 |
|
1598 ms |
71864 KB |
#pragma GCC optimize("Ofast")
#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
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) {
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) {
int essai = nextGreater(ptr + 1, getsum(L, ptr) + 1);
if(essai == ptr + 1) {
return ptr + 1;
}
ptr = essai - 1;
}
return n + 1;
}
int prevBreaker(int R, int start) {
int ptr = start;
while(ptr > 1) {
int essai = prevGreater(ptr - 1, getsum(ptr, R) + 1);
if(essai == ptr - 1) {
return ptr - 1;
}
ptr = essai + 1;
}
return 0;
}
}
vector<pii> getIntervs(int P) {
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;
if(nvR == R && fail) {
elems.emplace_back(L, R);
if((L != 1 && a[L - 1] <= a[R + 1]) || R == n) L--;
else R++;
fail = 0;
}
else { fail = R == nvR; R = nvR; }
}
else {
int nvL = prevBreaker(R, L) + 1;
if(nvL == L && fail) {
elems.emplace_back(L, R);
if((L != 1 && a[L - 1] <= a[R + 1]) || R == n) L--;
else R++;
fail = 0;
}
else {fail = L == nvL; L = nvL; }
}
direction *= -1;
}
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;
V.reserve(60);
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;
}
l = answer;
answer = ptr = r;
while(ptr >= l) {
ptr = Finders::prevBreaker(r, ptr);
if(ptr >= l) answer = ptr;
}
r = answer;
MinCounter cnt(1e9 + 5, -1, 0), cnt2;
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);
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;});
vector<pii> V, T;
for(int i = 1; i <= n; i++) {
T = getIntervs(i);
copy(all(T), back_inserter(V));
}
for(auto [l, r] : V) {
Segments::insert(l, r);
}
int q;
cin >> q;
for(int TC = 0, t, x, y; TC < q; TC++) {
cin >> t >> x >> y;
if(t == 1)
updPoz(x, y);
else
cout << query(x, y) << '\n';
}
}
/**
Anul asta se da centroid.
-- Surse oficiale
*/
Compilation message
fish2.cpp: In instantiation of 'tii AINT<Node>::getsons(int, int, int) [with Node = Sum; tii = std::tuple<int, int, int>]':
fish2.cpp:41:24: required from 'void AINT<Node>::walk(CB&&, int, int, int) [with int ismutable = 0; int toRight = 0; CB = getsum(int, int)::<lambda(Sum&, int, int)>&; Node = Sum]'
fish2.cpp:30:50: required from 'void AINT<Node>::walk(int, int, CB&&) [with CB = getsum(int, int)::<lambda(Sum&, int, int)>; Node = Sum]'
fish2.cpp:98:141: required from here
fish2.cpp:27:56: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
27 | 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 = GreaterFinder; tii = std::tuple<int, int, int>]':
fish2.cpp:41: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:30:50: required from 'void AINT<Node>::walk(int, int, CB&&) [with CB = Finders::nextGreater(int, int)::<lambda(GreaterFinder&, int, int)>; Node = GreaterFinder]'
fish2.cpp:113:171: required from here
fish2.cpp:27:56: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
fish2.cpp: In instantiation of 'tii AINT<Node>::getsons(int, int, int) [with Node = MinCounter; tii = std::tuple<int, int, int>]':
fish2.cpp:41: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:30:50: required from 'void AINT<Node>::walk(int, int, CB&&) [with CB = Segments::erase(int, int)::<lambda(MinCounter&, int, int)>; Node = MinCounter]'
fish2.cpp:202:8: required from here
fish2.cpp:27:56: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
28 ms |
756 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1598 ms |
71864 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
28 ms |
756 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1598 ms |
71864 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1598 ms |
71864 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
28 ms |
756 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
