oj.uz

Submission #649564

# Submission time Handle Problem Language Result Execution time Memory
649564 2022-10-10T15:21:44 Z lalala56 Monkey and Apple-trees (IZhO12_apple) C++14
100 / 100
 395 ms 188664 KB 
#include<bits/stdc++.h>
using namespace std;
const int M=1e9,N=123456;
struct Node{
    int sum,la,l,r,sl,sr;
    Node(): sum(0),la(0),l(-1),r(-1){}
};
Node ST[64*N];
int n,c,cnt=2;
void tao(int id,int m){
    //cout<<m<<'\n';
    if(ST[id].l==-1){
        ST[id].l=cnt++;
        ST[ST[id].l].sl=ST[id].sl;
        ST[ST[id].l].sr=m;
    }
    if(ST[id].r==-1){
        ST[id].r=cnt++;
        ST[ST[id].r].sl=m+1;
        ST[ST[id].r].sr=ST[id].sr;
    }
}
void down(int id){
    if(ST[id].la){
        ST[id].sum=ST[id].sr-ST[id].sl+1;
        int m=(ST[id].sl+ST[id].sr)/2;
        tao(id,m);
        ST[ST[id].l].la=ST[ST[id].r].la=1;
        ST[id].la=0;        
    }
}
void upd(int id,int l,int r){
    //cout<<id<<" "<<ST[id].sl<<" "<<ST[id].sr<<'\n';
    down(id);
    if(l==ST[id].sl&&r==ST[id].sr){
        //ST[id].sum=ST[id].sr-ST[id].sl+1;
        ST[id].la=1;
        down(id);
        return;
        
    }
    down(id);
    int m=(ST[id].sl+ST[id].sr)/2;
    tao(id,m);
    if(l>m)upd(ST[id].r,l,r);
    else if(r<=m)upd(ST[id].l,l,r);
    else{
        upd(ST[id].l,l,m);
        upd(ST[id].r,m+1,r);
    }
    down(ST[id].l);
    down(ST[id].r);
    ST[id].sum=ST[ST[id].l].sum+ST[ST[id].r].sum;
}
int findd(int id,int l,int r){
    down(id);
    if(l==ST[id].sl&&r==ST[id].sr)return ST[id].sum;
    
    int m=(ST[id].sl+ST[id].sr)/2;
    tao(id,m);
    if(l>m)return findd(ST[id].r,l,r);
    else if(r<=m)return findd(ST[id].l,l,r);
    else return findd(ST[id].l,l,m)+findd(ST[id].r,m+1,r);
}
void giai(){
    cin>>n;
    int k,x,y;
    c=0;
    ST[1].sum=0;ST[1].la=0;
    ST[1].sl=1;ST[1].sr=M;
    while(n--){
        cin>>k>>x>>y;
        if(k==1){
            c=findd(1,x+c,y+c);
            cout<<c<<'\n';
        }
        else upd(1,x+c,y+c);
       // cout<<"L\n";
    }
}
int main(){
    if(fopen("solve.inp","r")){
        freopen("solve.inp","r",stdin);
        freopen("solve.out","w",stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    giai();
}

Compilation message

apple.cpp: In function 'int main()':
apple.cpp:83:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         freopen("solve.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
apple.cpp:84:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         freopen("solve.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 185816 KB Output is correct
2 Correct 80 ms 185828 KB Output is correct
3 Correct 74 ms 185828 KB Output is correct
4 Correct 88 ms 185988 KB Output is correct
5 Correct 88 ms 185972 KB Output is correct
6 Correct 87 ms 185948 KB Output is correct
7 Correct 90 ms 185896 KB Output is correct
8 Correct 193 ms 186060 KB Output is correct
9 Correct 322 ms 186320 KB Output is correct
10 Correct 313 ms 186244 KB Output is correct
11 Correct 332 ms 186312 KB Output is correct
12 Correct 313 ms 186316 KB Output is correct
13 Correct 283 ms 186448 KB Output is correct
14 Correct 290 ms 186396 KB Output is correct
15 Correct 391 ms 188560 KB Output is correct
16 Correct 382 ms 188424 KB Output is correct
17 Correct 301 ms 188516 KB Output is correct
18 Correct 295 ms 188364 KB Output is correct
19 Correct 394 ms 188512 KB Output is correct
20 Correct 395 ms 188664 KB Output is correct