oj.uz

Submission #555079

# Submission time Handle Problem Language Result Execution time Memory
555079 2022-04-30T06:36:06 Z new_acc Growing Trees (BOI11_grow) C++14
100 / 100
 206 ms 11504 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e6+10;
const int SS=1<<19;
const int INFi=2e9;
const ll INFl=1e13;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=1000696969;
const ll p=70032301;
const ull p2=913;
const int L=20;
int t[N],seg1[(SS<<1)+10],seg2[(SS<<1)+10],lazy[(SS<<1)+10];
void push(int v){
    seg1[(v<<1)]+=lazy[v],seg1[(v<<1)+1]+=lazy[v];
    seg2[(v<<1)]+=lazy[v],seg2[(v<<1)+1]+=lazy[v];
    lazy[(v<<1)]+=lazy[v],lazy[(v<<1)+1]+=lazy[v];
    lazy[v]=0;
}
void upd(int a,int b,int x,int p=0,int k=SS-1,int v=1){
    if(p>b or k<a) return;
    if(p>=a and k<=b){
        if(seg2[v]==INFi) seg2[v]=0,seg1[v]=0;
        lazy[v]+=x,seg1[v]+=x,seg2[v]+=x;
        return;
    }
    push(v);
    upd(a,b,x,p,(p+k)>>1,(v<<1)),upd(a,b,x,((p+k)>>1)+1,k,(v<<1)+1);
    seg1[v]=max(seg1[v<<1],seg1[(v<<1)+1]);
    seg2[v]=min(seg2[v<<1],seg2[(v<<1)+1]);
}
int Query1(int x,int v=1){
    if(v>SS) return v-SS;
    push(v);
    if(seg1[(v<<1)]>=x) return Query1(x,(v<<1));
    else return Query1(x,(v<<1)+1);
}
int Query2(int x,int v=1){
    if(v>SS) return v-SS;
    push(v);
    if(seg2[(v<<1)+1]<=x) return Query2(x,(v<<1)+1);
    else return Query2(x,(v<<1));
}
int Query3(int x,int p=0,int k=SS-1,int v=1){
    if(p==k) return seg2[v];
    push(v);
    int sr=(p+k)>>1;
    if(x>sr) return Query3(x,sr+1,k,(v<<1)+1);
    else return Query3(x,p,sr,(v<<1));
}
void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>t[i];
    for(int i=1;i<=(SS<<1);i++) seg2[i]=INFi,seg1[i]=-1;
    sort(t+1,t+1+n);
    for(int i=1;i<=n;i++) upd(i,i,t[i]);
    for(int i=1;i<=m;i++){
        char a;
        cin>>a;
        if(a=='F'){
            int b,c;
            cin>>c>>b;
            if(seg1[1]<b) continue;
            int curr1=Query1(b),val=seg1[curr1+SS];
            int curr2=Query2(val);
            c=min(c,n-curr1+1);
            if(curr2-curr1+1>=c) upd(curr2-c+1,curr2,1); 
            else{
                c-=(curr2-curr1+1);
                int val2=Query3(curr2+c);
                int wsk1=Query1(val2),dl=curr2+c-wsk1+1,wsk2=Query2(val2);
                upd(wsk2-dl+1,wsk2,1),upd(curr2+1,wsk1-1,1),upd(curr1,curr2,1);
            }
        }else{
            int b,c;
            cin>>b>>c;
            if(b>seg1[1] or c<seg2[1]){
                cout<<0<<"\n";
                continue;
            }
            cout<<Query2(c)-Query1(b)+1<<"\n";
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    int tt=1;
    while(tt--) solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 10032 KB Output is correct
2 Correct 147 ms 11312 KB Output is correct
3 Correct 187 ms 11240 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8532 KB Output is correct
2 Correct 6 ms 8664 KB Output is correct
3 Correct 6 ms 8660 KB Output is correct
4 Correct 7 ms 8532 KB Output is correct
5 Correct 52 ms 9688 KB Output is correct
6 Correct 64 ms 9880 KB Output is correct
7 Correct 10 ms 8668 KB Output is correct
8 Correct 32 ms 9332 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 9260 KB Output is correct
2 Correct 64 ms 9972 KB Output is correct
3 Correct 7 ms 8660 KB Output is correct
4 Correct 40 ms 9668 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 9392 KB Output is correct
2 Correct 72 ms 9992 KB Output is correct
3 Correct 17 ms 8708 KB Output is correct
4 Correct 64 ms 10060 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 9800 KB Output is correct
2 Correct 126 ms 10800 KB Output is correct
3 Correct 23 ms 9112 KB Output is correct
4 Correct 149 ms 10792 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 9804 KB Output is correct
2 Correct 121 ms 10872 KB Output is correct
3 Correct 184 ms 11000 KB Output is correct
4 Correct 22 ms 9156 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 10048 KB Output is correct
2 Correct 98 ms 10868 KB Output is correct
3 Correct 201 ms 11220 KB Output is correct
4 Correct 20 ms 9120 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 10012 KB Output is correct
2 Correct 120 ms 10716 KB Output is correct
3 Correct 68 ms 10496 KB Output is correct
4 Correct 82 ms 10932 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 10196 KB Output is correct
2 Correct 129 ms 11212 KB Output is correct
3 Correct 206 ms 11504 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 10540 KB Output is correct