Submission #355626

# Submission time Handle Problem Language Result Execution time Memory
355626 2021-01-22T21:25:09 Z AmineTrabelsi Monkey and Apple-trees (IZhO12_apple) C++14
0 / 100
48 ms 17004 KB
#include "bits/stdc++.h"
using namespace std;
// Hi 
const int M = 1e6;
int a[M+5],tree[M*4],mark[M*4];
void push(int v){
    if(mark[v]){
        tree[v*2] = tree[v*2+1] = tree[v];
        mark[v*2] = mark[v*2+1] = 1;
        mark[v] = 0;
    }
}
void range_update(int v,int tl,int tr,int ql,int qr){
    if(ql > qr)return;
    if(ql == tl && qr == tr){
        tree[v] = 1;
        mark[v] = 1;
    }else{
        push(v);
        int mid = (tl+tr)/2;
        range_update(v*2,tl,mid,ql,min(qr,mid));
        range_update(v*2+1,mid+1,tr,max(mid+1,ql),qr);
    }
}
int range_query(int v,int tl,int tr,int ql,int qr){
    if(tl > qr || tr < ql)return 0;
    if(tl >= ql && tr <= qr && mark[v]){
        return tr-tl+1;
    }
    if(tl == tr)return mark[v];
    push(v);
    int mid = (tl+tr)/2;
    return range_query(v*2,tl,mid,ql,min(qr,mid))+
            range_query(v*2+1,mid+1,tr,max(ql,mid+1),qr);
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int q;
    cin>>q;
    int c =  0;
    while(q--){
        int t;
        cin>>t;
        if(t == 1){
            int x,y;
            cin>>x>>y;
            x += c-1;
            y += c-1;
            int ans = range_query(1,0,M-1,x,y);
            c = ans;
            cout << ans << '\n';
        }else{
            int x,y;
            cin>>x>>y;
            x += c-1;
            y += c-1;
            range_update(1,0,M-1,x,y);
        }
    }
    return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 48 ms 15340 KB Output is correct
5 Correct 28 ms 17004 KB Output is correct
6 Correct 26 ms 15340 KB Output is correct
7 Correct 40 ms 16876 KB Output is correct
8 Runtime error 12 ms 492 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -