| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 615983 |
2022-07-31T17:14:46 Z |
cheissmart |
Fish 2 (JOI22_fish2) |
C++14 |
|
4000 ms |
34464 KB |
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
const int INF = 1e9 + 7, N = 1e5 + 7;
const ll oo = 1e18;
ll a[N];
int n;
namespace cover {
pi t[N * 4];
int lz[N * 4];
pi add(pi a, pi b) {
if(a.F != b.F) return min(a, b);
a.S += b.S;
return a;
}
void apply(int v, int x) {
t[v].F += x;
lz[v] += x;
}
void push(int v) {
apply(v * 2, lz[v]);
apply(v * 2 + 1, lz[v]);
lz[v] = 0;
}
void build(int v = 1, int tl = 1, int tr = n + 1) {
for(int i = 1; i <= n; i++)
t[i] = {0, 1};
if(tr - tl == 1) {
t[v] = {0, 1};
return;
}
int tm = (tl + tr) / 2;
build(v * 2, tl, tm);
build(v * 2 + 1, tm, tr);
t[v] = add(t[v * 2], t[v * 2 + 1]);
}
void add(int l, int r, int x, int v = 1, int tl = 1, int tr = n + 1) {
if(l <= tl && tr <= r) {
apply(v, x);
return;
}
push(v);
int tm = (tl + tr) / 2;
if(l < tm) add(l, r, x, v * 2, tl, tm);
if(r > tm) add(l, r, x, v * 2 + 1, tm, tr);
t[v] = add(t[v * 2], t[v * 2 + 1]);
}
pi qry(int l, int r, int v = 1, int tl = 1, int tr = n + 1) {
if(l <= tl && tr <= r)
return t[v];
push(v);
int tm = (tl + tr) / 2;
pi res = {INF, INF};
if(l < tm) res = add(res, qry(l, r, v * 2, tl, tm));
if(r > tm) res = add(res, qry(l, r, v * 2 + 1, tm, tr));
return res;
}
}
namespace seg {
struct node {
V<pair<int, ll>> bad_pref, bad_suff;
V<pi> bad_seg;
ll sum;
} t[N * 4];
void pull(int v) {
for(auto p:t[v * 2].bad_pref)
t[v].bad_pref.PB(p);
for(auto p:t[v * 2 + 1].bad_suff)
t[v].bad_suff.PB(p);
for(auto[pos, sum]:t[v * 2 + 1].bad_pref) if(sum + t[v * 2].sum < a[pos + 1])
t[v].bad_pref.EB(pos, sum + t[v * 2].sum);
for(auto[pos, sum]:t[v * 2].bad_suff) if(sum + t[v * 2 + 1].sum < a[pos - 1])
t[v].bad_suff.EB(pos, sum + t[v * 2 + 1].sum);
for(int i = 0, j = 0; i < SZ(t[v * 2].bad_suff) && j < SZ(t[v * 2 + 1].bad_pref); ) {
auto he = t[v * 2].bad_suff[i], be = t[v * 2 + 1].bad_pref[j];
if(he.S + be.S < min(a[he.F - 1], a[be.F + 1]))
t[v].bad_seg.EB(he.F, be.F);
if(a[he.F - 1] < a[be.F + 1])
i++;
else
j++;
}
t[v].sum = t[v * 2].sum + t[v * 2 + 1].sum;
}
void build(int v = 1, int tl = 1, int tr = n + 1) {
if(tr - tl == 1) {
t[v].sum = a[tl];
if(a[tl] < a[tl + 1])
t[v].bad_pref.EB(tl, a[tl]);
if(a[tl] < a[tl - 1])
t[v].bad_suff.EB(tl, a[tl]);
if(a[tl] < a[tl + 1] && a[tl] < a[tl - 1])
t[v].bad_seg.EB(tl, tl);
} else {
int tm = (tl + tr) / 2;
build(v * 2, tl, tm);
build(v * 2 + 1, tm, tr);
pull(v);
}
for(auto[l, r]:t[v].bad_seg)
cover::add(l, r + 1, 1);
}
void upd(int pos, int v = 1, int tl = 1, int tr = n + 1) {
for(auto[l, r]:t[v].bad_seg)
cover::add(l, r + 1, -1);
t[v].bad_seg.clear(), t[v].bad_pref.clear(), t[v].bad_suff.clear();
if(tr - tl == 1) {
t[v].sum = a[tl];
if(a[tl] < a[tl + 1])
t[v].bad_pref.EB(tl, a[tl]);
if(a[tl] < a[tl - 1])
t[v].bad_suff.EB(tl, a[tl]);
if(a[tl] < a[tl + 1] && a[tl] < a[tl - 1])
t[v].bad_seg.EB(tl, tl);
} else {
int tm = (tl + tr) / 2;
if(pos - 1 < tm)
upd(pos, v * 2, tl, tm);
if(pos + 1 >= tm)
upd(pos, v * 2 + 1, tm, tr);
pull(v);
}
for(auto[l, r]:t[v].bad_seg)
cover::add(l, r + 1, 1);
}
}
void upd(int pos, ll val) {
a[pos] = val;
seg::upd(pos);
}
signed main()
{
IO_OP;
cin >> n;
a[0] = a[n + 1] = oo;
for(int i = 1; i <= n; i++)
cin >> a[i];
cover::build();
seg::build();
int q;
cin >> q;
while(q--) {
int op;
cin >> op;
if(op == 1) {
int x, y;
cin >> x >> y;
upd(x, y);
} else {
int l, r;
cin >> l >> r;
ll tl = a[l - 1], tr = a[r + 1];
if(l - 1 >= 1) upd(l - 1, 1e15);
if(r + 1 <= n) upd(r + 1, 1e15);
pi p = cover::qry(l, r + 1);
cout << p.S << '\n';
if(l - 1 >= 1) upd(l - 1, tl);
if(r + 1 <= n) upd(r + 1, tr);
}
}
}
Compilation message
fish2.cpp: In function 'void seg::pull(int)':
fish2.cpp:88:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
88 | for(auto[pos, sum]:t[v * 2 + 1].bad_pref) if(sum + t[v * 2].sum < a[pos + 1])
| ^
fish2.cpp:90:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
90 | for(auto[pos, sum]:t[v * 2].bad_suff) if(sum + t[v * 2 + 1].sum < a[pos - 1])
| ^
fish2.cpp: In function 'void seg::build(int, int, int)':
fish2.cpp:119:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
119 | for(auto[l, r]:t[v].bad_seg)
| ^
fish2.cpp: In function 'void seg::upd(int, int, int, int)':
fish2.cpp:123:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
123 | for(auto[l, r]:t[v].bad_seg)
| ^
fish2.cpp:143:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
143 | for(auto[l, r]:t[v].bad_seg)
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
31572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
31572 KB |
Output is correct |
| 2 |
Execution timed out |
4062 ms |
34464 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
31572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
31572 KB |
Output is correct |
| 2 |
Execution timed out |
4062 ms |
34464 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
31572 KB |
Output is correct |
| 2 |
Execution timed out |
4062 ms |
34464 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
31572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
