Submission #89809

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
89809	2018-12-18T12:41:28 Z	Vardanyan	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	570 ms	133340 KB

apple

#include <bits/stdc++.h>
using namespace std;
struct node{
    int val,lz;
};
const int N = 1000*1000+5;
node t[10*N];
int son1[10*N];
int son2[10*N];
int timer = 1;
void push(int v,int s,int e){
    if(t[v].lz!=0){
        t[v].val = (e-s+1)*(t[v].lz);
        if(s!=e){
            if(son1[v] == 0){
                son1[v] = ++timer;
                son2[v] = ++timer;
            }
            t[son1[v]].lz = 1;
            t[son2[v]].lz = 1;
              //  t[son1[v]]->lz = t[v].lz;
                //t[v].r->lz = t[v].lz;
        }
    }
    t[v].lz = 0;
}
void update(int v,int s,int e,int l,int r,int val){
    push(v,s,e);
    if(l>r) return;
    if(s == l && e == r){
        t[v].lz = val;
        return;
    }
    int m = (s+e)/2;
    if(son1[v] == 0){
        son1[v] = ++timer;
        son2[v] = ++timer;
    }
    update(son1[v],s,m,l,min(m,r),val);
    update(son2[v],m+1,e,max(l,m+1),r,val);
    push(son1[v],s,m);
    push(son2[v],m+1,e);
    t[v].val = t[son1[v]].val+t[son2[v]].val;
}
int get(int v,int s,int e,int l,int r){
    push(v,s,e);
    if(l>r) return 0;
    if(s == l && e == r) return t[v].val;
    int m = (s+e)/2;
    return get(son1[v],s,m,l,min(m,r))+
           get(son2[v],m+1,e,max(l,m+1),r);
}
int main(){

    int m;
    scanf("%d",&m);
    int C = 0;
    while(m--){
        int d,x,y;
        scanf("%d%d%d",&d,&x,&y);
        if(d == 1){
            int ans = get(1,1,1000*1000*1000,x+C,y+C);
            C = ans;
            printf("%d\n",ans);
        }
        else{
            update(1,1,1000*1000*1000,x+C,y+C,1);
        }
    }

    return 0;
}

Compilation message

apple.cpp: In function 'int main()':
apple.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&m);
     ~~~~~^~~~~~~~~
apple.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&d,&x,&y);
         ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	496 KB	Output is correct
3	Correct	2 ms	576 KB	Output is correct
4	Correct	17 ms	3312 KB	Output is correct
5	Correct	20 ms	4028 KB	Output is correct
6	Correct	20 ms	4028 KB	Output is correct
7	Correct	20 ms	4028 KB	Output is correct
8	Correct	161 ms	26268 KB	Output is correct
9	Correct	344 ms	44584 KB	Output is correct
10	Correct	365 ms	49800 KB	Output is correct
11	Correct	347 ms	53968 KB	Output is correct
12	Correct	369 ms	55880 KB	Output is correct
13	Correct	333 ms	69284 KB	Output is correct
14	Correct	347 ms	70080 KB	Output is correct
15	Correct	540 ms	127036 KB	Output is correct
16	Correct	507 ms	127976 KB	Output is correct
17	Correct	309 ms	127976 KB	Output is correct
18	Correct	328 ms	127976 KB	Output is correct
19	Correct	501 ms	130888 KB	Output is correct
20	Correct	570 ms	133340 KB	Output is correct