oj.uz

Submission #878538

# Submission time Handle Problem Language Result Execution time Memory
878538 2023-11-24T16:40:46 Z winter0101 Fire (JOI20_ho_t5) C++14
100 / 100
 421 ms 77500 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define lastbit(i) __builtin_ctz(i)
const int maxn=2e5+9;
int a[maxn];
vector<pii>b[maxn];
struct BIT{
vector<long long>bit;
int n;
void resz(int _n){
n=_n;
bit.resize(n+1);
}
void add(int pos,long long val){
for(;pos<=n;pos+=(pos-(pos&(pos-1))))bit[pos]+=val;
}
long long get(int pos){
long long ans=0;
for(;pos>=1;pos-=(pos-(pos&(pos-1))))ans+=bit[pos];
return ans;
}
long long get(int l,int r){
if (l>r)return 0;
return get(r)-get(l-1);
}
};
int in[maxn],out[maxn],tme=0,st[maxn][19];
vector<pii>add[maxn],del[maxn],add2[maxn],del2[maxn];
long long ans[maxn];
BIT cnt,bit;
BIT t1,t2,t3,t4;
int n,q;
int par[maxn];
void predfs(int u){
in[u]=++tme;
for (auto v:add[u]){
int tmp=u;
for2(j,18,0){
if (!st[tmp][j]||!par[st[tmp][j]])continue;
int pr=par[st[tmp][j]];
if (v.fi+pr>=u){
tmp=st[tmp][j];
}
}
if (st[tmp][0]&&par[st[tmp][0]]&&v.fi+par[st[tmp][0]]<u){
tmp=st[tmp][0];
add2[tmp].pb(v);
//cout<<tmp<<'\n';
}
}
for (auto v:del[u]){
int tmp=u;
for2(j,18,0){
if (!st[tmp][j]||!par[st[tmp][j]])continue;
int pr=par[st[tmp][j]];
if (v.fi+pr>=u){
tmp=st[tmp][j];
}
}
if (st[tmp][0]&&par[st[tmp][0]]&&v.fi+par[st[tmp][0]]<u){
tmp=st[tmp][0];
del2[tmp].pb(v);
}
}
for (auto v:b[u]){
st[v.fi][0]=u;
for1(i,1,18)st[v.fi][i]=st[st[v.fi][i-1]][i-1];
predfs(v.fi);
}
out[u]=tme;
}
void solve(int u){
if (par[u]){
int diff=par[u];
long long w=a[par[u]]-a[u];
t1.add(diff,-w*(u-1));
t2.add(diff,w);
diff=u-par[u];
t3.add(diff,-1ll*w*(diff-1));
t4.add(diff,w);
}
for (auto v:add2[u]){
ans[v.se]+=1ll*v.fi*t4.get(v.fi)+t3.get(v.fi);
}
for (auto v:del2[u]){
ans[v.se]-=1ll*v.fi*t4.get(v.fi)+t3.get(v.fi);
}
for (auto v:add[u]){
//cout<<bit.get(v.fi)<<'\n';
ans[v.se]+=1ll*v.fi*cnt.get(v.fi)+bit.get(v.fi);
//cout<<max(u-v.fi,1)<<'\n';
//cout<<t2.get(n)<<'\n';
ans[v.se]+=1ll*u*t2.get(max(u-v.fi,1),n)+t1.get(max(u-v.fi,1),n);
}
for (auto v:del[u]){
ans[v.se]-=1ll*v.fi*cnt.get(v.fi)+bit.get(v.fi);
ans[v.se]-=1ll*u*t2.get(max(u-v.fi,1),n)+t1.get(max(u-v.fi,1),n);
}
for (auto v:b[u]){
solve(v.fi);
}
if (par[u]){
    int diff=par[u];
    long long w=a[par[u]]-a[u];
    t1.add(diff,w*(u-1));
    t2.add(diff,-w);
    diff=u-par[u];
    t3.add(diff,1ll*w*(diff-1));
    t4.add(diff,-w);
}
if (par[u]){
int sz=out[u]-in[u]+1;
int time=u-par[u];
bit.add(time+sz,1ll*(a[par[u]]-a[u])*sz);
long long value=(a[par[u]]-a[u]);
value*=(time-1);
//update poly
bit.add(time,-value);
bit.add(time+sz,value);
cnt.add(time,(a[par[u]]-a[u]));
cnt.add(time+sz,-(a[par[u]]-a[u]));
}
}
long long pf[maxn];
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    cin>>n>>q;
    cnt.resz(n);
    t3.resz(n);
    t4.resz(n);
    bit.resz(n);
    t1.resz(n);
    t2.resz(n);
    for1(i,1,n)cin>>a[i];
    for1(i,1,n)pf[i]=pf[i-1]+a[i];
    a[0]=1e9+7;
    stack<int>t;
    t.push(0);
    vector<int>root;
    for1(i,1,n){
    while (!t.empty()&&a[t.top()]<=a[i])t.pop();
    int p=t.top();
    if (p)b[p].pb({i,i-p});
    else root.pb(i);
    par[i]=t.top();
    t.push(i);
    }
    for1(i,1,q){
    int t,l,r;
    cin>>t>>l>>r;
    add[r].pb({t,i});
    del[l-1].pb({t,i});
    ans[i]+=pf[r]-pf[l-1];
    }
    for (auto v:root)predfs(v);
    for (auto v:root)solve(v);
    for1(i,1,q)cout<<ans[i]<<'\n';
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29532 KB Output is correct
2 Correct 6 ms 29800 KB Output is correct
3 Correct 7 ms 29788 KB Output is correct
4 Correct 6 ms 29788 KB Output is correct
5 Correct 6 ms 29788 KB Output is correct
6 Correct 6 ms 29788 KB Output is correct
7 Correct 6 ms 29768 KB Output is correct
8 Correct 6 ms 29788 KB Output is correct
9 Correct 6 ms 29788 KB Output is correct
10 Correct 6 ms 29788 KB Output is correct
11 Correct 7 ms 30040 KB Output is correct
12 Correct 6 ms 29788 KB Output is correct
13 Correct 6 ms 29788 KB Output is correct
14 Correct 6 ms 29788 KB Output is correct
15 Correct 6 ms 29788 KB Output is correct
16 Correct 6 ms 29788 KB Output is correct
17 Correct 6 ms 29788 KB Output is correct
18 Correct 6 ms 29788 KB Output is correct
19 Correct 6 ms 29788 KB Output is correct
20 Correct 7 ms 29788 KB Output is correct
21 Correct 7 ms 29800 KB Output is correct
22 Correct 7 ms 29788 KB Output is correct
23 Correct 8 ms 29788 KB Output is correct
24 Correct 6 ms 29788 KB Output is correct
25 Correct 6 ms 29788 KB Output is correct
26 Correct 6 ms 29788 KB Output is correct
27 Correct 6 ms 29788 KB Output is correct
28 Correct 6 ms 29716 KB Output is correct
29 Correct 6 ms 29788 KB Output is correct
30 Correct 7 ms 29724 KB Output is correct
31 Correct 6 ms 30040 KB Output is correct
32 Correct 6 ms 29788 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29532 KB Output is correct
2 Correct 360 ms 74380 KB Output is correct
3 Correct 323 ms 73812 KB Output is correct
4 Correct 343 ms 75032 KB Output is correct
5 Correct 341 ms 75416 KB Output is correct
6 Correct 353 ms 76828 KB Output is correct
7 Correct 357 ms 74380 KB Output is correct
8 Correct 325 ms 76068 KB Output is correct
9 Correct 408 ms 75264 KB Output is correct
10 Correct 326 ms 73880 KB Output is correct
11 Correct 375 ms 74564 KB Output is correct
12 Correct 313 ms 73808 KB Output is correct
13 Correct 387 ms 76236 KB Output is correct
14 Correct 326 ms 74960 KB Output is correct
15 Correct 338 ms 76268 KB Output is correct
16 Correct 361 ms 76960 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29532 KB Output is correct
2 Correct 391 ms 74992 KB Output is correct
3 Correct 374 ms 74504 KB Output is correct
4 Correct 370 ms 75680 KB Output is correct
5 Correct 385 ms 74064 KB Output is correct
6 Correct 347 ms 74328 KB Output is correct
7 Correct 388 ms 74576 KB Output is correct
8 Correct 421 ms 74700 KB Output is correct
9 Correct 355 ms 74068 KB Output is correct
10 Correct 346 ms 73812 KB Output is correct
11 Correct 368 ms 75208 KB Output is correct
12 Correct 373 ms 74788 KB Output is correct
13 Correct 357 ms 75128 KB Output is correct
14 Correct 369 ms 73688 KB Output is correct
15 Correct 374 ms 74676 KB Output is correct
16 Correct 348 ms 74700 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 68960 KB Output is correct
2 Correct 304 ms 69060 KB Output is correct
3 Correct 349 ms 69732 KB Output is correct
4 Correct 327 ms 68904 KB Output is correct
5 Correct 317 ms 69220 KB Output is correct
6 Correct 316 ms 69132 KB Output is correct
7 Correct 271 ms 69580 KB Output is correct
8 Correct 296 ms 69580 KB Output is correct
9 Correct 284 ms 69388 KB Output is correct
10 Correct 328 ms 69432 KB Output is correct
11 Correct 293 ms 69436 KB Output is correct
12 Correct 315 ms 69684 KB Output is correct
13 Correct 297 ms 69432 KB Output is correct
14 Correct 299 ms 69536 KB Output is correct

Subtask #5
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29532 KB Output is correct
2 Correct 6 ms 29800 KB Output is correct
3 Correct 7 ms 29788 KB Output is correct
4 Correct 6 ms 29788 KB Output is correct
5 Correct 6 ms 29788 KB Output is correct
6 Correct 6 ms 29788 KB Output is correct
7 Correct 6 ms 29768 KB Output is correct
8 Correct 6 ms 29788 KB Output is correct
9 Correct 6 ms 29788 KB Output is correct
10 Correct 6 ms 29788 KB Output is correct
11 Correct 7 ms 30040 KB Output is correct
12 Correct 6 ms 29788 KB Output is correct
13 Correct 6 ms 29788 KB Output is correct
14 Correct 6 ms 29788 KB Output is correct
15 Correct 6 ms 29788 KB Output is correct
16 Correct 6 ms 29788 KB Output is correct
17 Correct 6 ms 29788 KB Output is correct
18 Correct 6 ms 29788 KB Output is correct
19 Correct 6 ms 29788 KB Output is correct
20 Correct 7 ms 29788 KB Output is correct
21 Correct 7 ms 29800 KB Output is correct
22 Correct 7 ms 29788 KB Output is correct
23 Correct 8 ms 29788 KB Output is correct
24 Correct 6 ms 29788 KB Output is correct
25 Correct 6 ms 29788 KB Output is correct
26 Correct 6 ms 29788 KB Output is correct
27 Correct 6 ms 29788 KB Output is correct
28 Correct 6 ms 29716 KB Output is correct
29 Correct 6 ms 29788 KB Output is correct
30 Correct 7 ms 29724 KB Output is correct
31 Correct 6 ms 30040 KB Output is correct
32 Correct 6 ms 29788 KB Output is correct
33 Correct 360 ms 74380 KB Output is correct
34 Correct 323 ms 73812 KB Output is correct
35 Correct 343 ms 75032 KB Output is correct
36 Correct 341 ms 75416 KB Output is correct
37 Correct 353 ms 76828 KB Output is correct
38 Correct 357 ms 74380 KB Output is correct
39 Correct 325 ms 76068 KB Output is correct
40 Correct 408 ms 75264 KB Output is correct
41 Correct 326 ms 73880 KB Output is correct
42 Correct 375 ms 74564 KB Output is correct
43 Correct 313 ms 73808 KB Output is correct
44 Correct 387 ms 76236 KB Output is correct
45 Correct 326 ms 74960 KB Output is correct
46 Correct 338 ms 76268 KB Output is correct
47 Correct 361 ms 76960 KB Output is correct
48 Correct 391 ms 74992 KB Output is correct
49 Correct 374 ms 74504 KB Output is correct
50 Correct 370 ms 75680 KB Output is correct
51 Correct 385 ms 74064 KB Output is correct
52 Correct 347 ms 74328 KB Output is correct
53 Correct 388 ms 74576 KB Output is correct
54 Correct 421 ms 74700 KB Output is correct
55 Correct 355 ms 74068 KB Output is correct
56 Correct 346 ms 73812 KB Output is correct
57 Correct 368 ms 75208 KB Output is correct
58 Correct 373 ms 74788 KB Output is correct
59 Correct 357 ms 75128 KB Output is correct
60 Correct 369 ms 73688 KB Output is correct
61 Correct 374 ms 74676 KB Output is correct
62 Correct 348 ms 74700 KB Output is correct
63 Correct 335 ms 68960 KB Output is correct
64 Correct 304 ms 69060 KB Output is correct
65 Correct 349 ms 69732 KB Output is correct
66 Correct 327 ms 68904 KB Output is correct
67 Correct 317 ms 69220 KB Output is correct
68 Correct 316 ms 69132 KB Output is correct
69 Correct 271 ms 69580 KB Output is correct
70 Correct 296 ms 69580 KB Output is correct
71 Correct 284 ms 69388 KB Output is correct
72 Correct 328 ms 69432 KB Output is correct
73 Correct 293 ms 69436 KB Output is correct
74 Correct 315 ms 69684 KB Output is correct
75 Correct 297 ms 69432 KB Output is correct
76 Correct 299 ms 69536 KB Output is correct
77 Correct 379 ms 74892 KB Output is correct
78 Correct 415 ms 75832 KB Output is correct
79 Correct 362 ms 75216 KB Output is correct
80 Correct 371 ms 75000 KB Output is correct
81 Correct 348 ms 75308 KB Output is correct
82 Correct 400 ms 75776 KB Output is correct
83 Correct 386 ms 75668 KB Output is correct
84 Correct 366 ms 74616 KB Output is correct
85 Correct 420 ms 75336 KB Output is correct
86 Correct 394 ms 76068 KB Output is correct
87 Correct 348 ms 74624 KB Output is correct
88 Correct 333 ms 74832 KB Output is correct
89 Correct 325 ms 73404 KB Output is correct
90 Correct 342 ms 74352 KB Output is correct
91 Correct 351 ms 73952 KB Output is correct
92 Correct 349 ms 73548 KB Output is correct
93 Correct 339 ms 74268 KB Output is correct
94 Correct 327 ms 74704 KB Output is correct
95 Correct 356 ms 75100 KB Output is correct
96 Correct 349 ms 74068 KB Output is correct
97 Correct 344 ms 74068 KB Output is correct
98 Correct 340 ms 76752 KB Output is correct
99 Correct 356 ms 77012 KB Output is correct
100 Correct 374 ms 77500 KB Output is correct
101 Correct 362 ms 76936 KB Output is correct
102 Correct 360 ms 77380 KB Output is correct