| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1113285 |
2024-11-16T09:42:44 Z |
dwuy |
Fish 2 (JOI22_fish2) |
C++14 |
|
223 ms |
53208 KB |
/** - dwuy -
／＞ フ
| _ _|
／`ミ _x ノ
/ |
/ ヽ ?
／￣| | | |
| (￣ヽ＿_ヽ_)_)
＼二つ
**/
#include <bits/stdc++.h>
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) (int)((s).size())
#define MASK(k)(1LL<<(k))
#define TASK "test"
#define int long long
using namespace std;
typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;
const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX = 100005;
int n;
int a[MX];
struct Tnode{
int mx, sum;
};
struct Taiki{
int n;
vector<Tnode> tree;
Taiki(int n = 0) : n(n), tree(n<<2|3, {0, 0}) {}
Tnode combine(Tnode a, Tnode b){
return {max(a.mx, b.mx), a.sum + b.sum};
}
void update(int pos, int val){
int id = 1;
for(int lo=1, hi=n; lo<hi;){
int mid = (lo + hi)>>1;
if(pos <= mid) hi = mid, id = id<<1;
else lo = mid + 1, id = id<<1|1;
}
tree[id] = {val, val};
for(id>>=1; id; id>>=1) tree[id] = combine(tree[id<<1], tree[id<<1|1]);
}
int gsum(int l, int r, int id, const int &u, const int &v){
if(l > v || r < u) return 0;
if(l >= u && r <= v) return tree[id].sum;
int mid = (l + r)>>1;
return gsum(l, mid, id<<1, u, v) + gsum(mid + 1, r, id<<1|1, u, v);
}
int gsum(int l, int r){
return gsum(1, n, 1, l, r);
}
int lmx(int l, int r, int id, const int &pos, const int &val){
if(l > pos || tree[id].mx <= val) return l - 1;
if(l == r) return l;
int mid = (l + r)>>1;
int p = lmx(mid + 1, r, id<<1|1, pos, val);
return p != mid? p : lmx(l, mid, id<<1, pos, val);
}
int lmx(int pos, int val){
return lmx(1, n, 1, pos, val);
}
int rmx(int l, int r, int id, const int &pos, const int &val){
if(r < pos || tree[id].mx <= val) return r + 1;
if(l == r) return l;
int mid = (l + r)>>1;
int p = rmx(l, mid, id<<1, pos, val);
return p != mid + 1? p : rmx(mid + 1, r, id<<1|1, pos, val);
}
int rmx(int pos, int val){
return rmx(1, n, 1, pos, val);
}
} taiki;
struct Cnode{
vector<pii> pl, pr;
int l, r;
/// pl: {pl[i], ...} -> pr[i] = R;
/// pr: {pr[i], ...} -> pl[i] = L;
Cnode() : pl({}), pr({}), l(0), r(0) {}
};
struct Chii{
int n;
vector<Cnode> tree;
Chii(int n = 0) : n(n), tree(n<<2|3, Cnode()) {}
void build(int l, int r, int id){
tree[id].l = l;
tree[id].r = r;
if(l == r) return;
int mid = (l + r)>>1;
build(l, mid, id<<1);
build(mid + 1, r, id<<1|1);
}
void build(){
build(1, n, 1);
}
Cnode combine(Cnode a, Cnode b){
Cnode res;
res.l = a.l;
res.r = b.r;
if(a.pl.size() == 0 || b.pl.size() == 0) return res;
res.pr = a.pr;
res.pr.pop_back();
res.pl = b.pl;
res.pl.pop_back();
int bsum = taiki.gsum(b.l, b.pr[0].fi);
for(int i=0, j=b.l - 1; i<len(b.pr);){
int p = taiki.lmx(j, bsum);
p = max(p, a.l - 1);
if(p != j){
bsum += taiki.gsum(p + 1, j);
j = p;
while(i + 1 < len(b.pr) && bsum >= ::a[b.pr[i].fi + 1]){
b.pr[i + 1].se += b.pr[i].se;
bsum += taiki.gsum(b.pr[i].fi + 1, b.pr[i + 1].fi);
i++;
}
if(j < a.l){
while(i < len(b.pr)){
res.pr.push_back(b.pr[i]);
i++;
}
res.pl.push_back({j + 1, b.pr.back().se});
}
}
else{
i++;
if(i == len(b.pr)) res.pl.push_back({j + 1, b.pr.back().se});
else bsum += taiki.gsum(b.pr[i - 1].fi + 1, b.pr[i].fi);
}
}
bsum = taiki.gsum(a.pl[0].fi, a.r);
for(int i=0, j=a.r + 1; i<len(a.pl); ){
int p = taiki.rmx(j, bsum);
p = min(p, b.r + 1);
if(p != j){
bsum += taiki.gsum(j, p - 1);
j = p;
while(i + 1 <len(a.pl) && bsum >= ::a[a.pl[i].fi - 1]){
a.pl[i + 1].se += a.pl[i].se;
bsum += taiki.gsum(a.pl[i + 1].fi, a.pl[i].fi - 1);
i++;
}
if(j > b.r){
while(i < len(a.pl)){
res.pl.push_back(a.pl[i]);
i++;
}
res.pr.push_back({j - 1, a.pl.back().se});
}
}
else{
i++;
if(i == len(a.pl)) res.pr.push_back({j - 1, a.pl.back().se});
else bsum += taiki.gsum(a.pl[i].fi, a.pl[i - 1].fi - 1);
}
}
sort(res.pr.begin(), res.pr.end());
sort(res.pl.begin(), res.pl.end(), greater<pii>());
vector<pii> tmp;
for(pii p: res.pr){
if(tmp.size() && tmp.back().fi == p.fi) tmp.back().se += p.se;
else tmp.push_back(p);
}
res.pr = tmp;
tmp.clear();
for(pii p: res.pl){
if(tmp.size() && tmp.back().fi == p.fi) tmp.back().se += p.se;
else tmp.push_back(p);
}
res.pl = tmp;
return res;
}
void update(int pos, int val){
int id = 1;
for(int lo=1, hi=n; lo<hi;){
int mid = (lo + hi)>>1;
if(pos <= mid) hi = mid, id = id<<1;
else lo = mid + 1, id = id<<1|1;
}
tree[id].pl = {{pos, 1}};
tree[id].pr = {{pos, 1}};
// cout << id << " - " << tree[id].l << ' ' << tree[id].r << ' ' << pos << endl;
for(id>>=1; id; id>>=1) tree[id] = combine(tree[id<<1], tree[id<<1|1]);
}
Cnode get(int l, int r, int id, const int &u, const int &v){
if(l >= u && r <= v) return tree[id];
int mid = (l + r)>>1;
if(mid >= v) return get(l, mid, id<<1, u, v);
if(mid < u) return get(mid + 1, r, id<<1|1, u, v);
return combine(get(l, mid, id<<1, u, v), get(mid + 1, r, id<<1|1, u, v));
}
int get(int l, int r){
Cnode res = get(1, n, 1, l, r);
assert(res.pl.size());
return res.pl.back().se;
}
void show(int l, int r, int id){
cout << " === " << l << ' ' << r << endl;
cout << "pl: "; for(pii p: tree[id].pl) cout << "{" << p.fi << ", " << p.se << "} ";
cout << endl;
cout << "pr: "; for(pii p: tree[id].pr) cout << "{" << p.fi << ", " << p.se << "} ";
cout << endl << endl;
if(l == r) return;
int mid = (l + r)>>1;
show(l, mid, id<<1);
show(mid + 1, r, id<<1|1);
}
void show(){
show(1, n, 1);
}
} chii;
int32_t main(){
fastIO;
//file(TASK);
cin >> n;
for(int i=1; i<=n; i++) cin >> a[i];
taiki = Taiki(n);
chii = Chii(n);
chii.build();
for(int i=1; i<=n; i++) taiki.update(i, a[i]);
for(int i=1; i<=n; i++) chii.update(i, a[i]);
// chii.show();
int q; cin >> q;
while(q--){
int oper, u, v;
cin >> oper >> u >> v;
if(oper == 1){
a[u] = v;
taiki.update(u, a[u]);
chii.update(u, a[u]);
}
else{
cout << chii.get(u, v) << endl;
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
2 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
504 KB |
Output is correct |
| 5 |
Incorrect |
7 ms |
760 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
508 KB |
Output is correct |
| 2 |
Incorrect |
223 ms |
53208 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
2 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
504 KB |
Output is correct |
| 5 |
Incorrect |
7 ms |
760 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
508 KB |
Output is correct |
| 2 |
Incorrect |
223 ms |
53208 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
508 KB |
Output is correct |
| 2 |
Incorrect |
223 ms |
53208 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
2 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
504 KB |
Output is correct |
| 5 |
Incorrect |
7 ms |
760 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
