oj.uz

Submission #339945

# Submission time Handle Problem Language Result Execution time Memory
339945 2020-12-26T11:49:43 Z fixikmila Monkey and Apple-trees (IZhO12_apple) C++14
0 / 100
 228 ms 97644 KB 
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
typedef long long ll;
typedef pair<ll,ll>pll;
typedef long double ld;
ll bin_pow(ll a,ll b){
    if(b==0)return 1;
    if(b%2==0){
        ll t=bin_pow(a,b/2);
        return t*t%MOD;
    }
    else return a*bin_pow(a,b-1)%MOD;
}
struct cat{
int a,b,c,d;};
cat tree[3000001];
ll node=1;
void push(int v,int tl,int tr){
    if(tree[v].c==0)return;
    /*if(tree[v].a==0){
        node++;
        tree[v].a=node;
    }
    if(tree[v].b==0){
        node++;
        tree[v].b=node;
    }*/
    int tm=(tl+tr)/2;
    tree[tree[v].a].c=tree[tree[v].b].c=1;
    tree[tree[v].a].d=tm-tl+1;
    tree[tree[v].b].d=tr-(tm+1)+1;
    tree[v].c=0;
}
void update(int l,int r,int v,int tl,int tr){
    if(tl>=l&&tr<=r){
            tree[v].c=1;
            tree[v].d=tr-tl+1;
            return;
    }
    else if(tl>r||tr<l)return;
    if(tree[v].a==0){
        node++;
        tree[v].a=node;
    }
    if(tree[v].b==0){
        node++;
        tree[v].b=node;
    }
    int tm=(tl+tr)/2;
    push(v,tl,tr);
    update(l,r,tree[v].a,tl,tm),update(l,r,tree[v].b,tm+1,tr);
    tree[v].d=tree[tree[v].a].d+tree[tree[v].b].d;
}
ll get(int l,int r,int v,int tl,int tr){
    if(tl>=l&&tr<=r){
        return tree[v].d;
    }
    else if(tl>r||tr<l)return 0;
    int tm=(tl+tr)/2;
    if(tree[v].a==0){
        node++;
        tree[v].a=node;
    }
    if(tree[v].b==0){
        node++;
        tree[v].b=node;
    }
    push(v,tl,tr);
    return get(l,r,tree[v].a,tl,tm)+get(l,r,tree[v].b,tm+1,tr);
}
int main()
{
    //freopen("b.in","r",stdin);
    //freopen("b.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll t=1,n,m,k=0,sum=0 ,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>z>>x>>y;
        x+=ans;
        y+=ans;
        if(z==1){
            ans=get(x,y,1,1,1e9);
            cout<<ans;
            cout<<"\n";
        }
        else update(x,y,1,1,1e9);
    }
    return 0;
}

Compilation message

apple.cpp: In function 'int main()':
apple.cpp:78:8: warning: unused variable 't' [-Wunused-variable]
   78 |     ll t=1,n,m,k=0,sum=0 ,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |        ^
apple.cpp:78:14: warning: unused variable 'm' [-Wunused-variable]
   78 |     ll t=1,n,m,k=0,sum=0 ,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |              ^
apple.cpp:78:16: warning: unused variable 'k' [-Wunused-variable]
   78 |     ll t=1,n,m,k=0,sum=0 ,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                ^
apple.cpp:78:20: warning: unused variable 'sum' [-Wunused-variable]
   78 |     ll t=1,n,m,k=0,sum=0 ,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                    ^~~
apple.cpp:78:45: warning: unused variable 'mn' [-Wunused-variable]
   78 |     ll t=1,n,m,k=0,sum=0 ,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                                             ^~
apple.cpp:78:58: warning: unused variable 'mx' [-Wunused-variable]
   78 |     ll t=1,n,m,k=0,sum=0 ,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                                                          ^~

Subtask #1
0 / 100.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 10 ms 1900 KB Output is correct
5 Correct 13 ms 2284 KB Output is correct
6 Correct 13 ms 2156 KB Output is correct
7 Correct 13 ms 2284 KB Output is correct
8 Correct 91 ms 15084 KB Output is correct
9 Correct 193 ms 27628 KB Output is correct
10 Correct 197 ms 30316 KB Output is correct
11 Correct 204 ms 32364 KB Output is correct
12 Correct 213 ms 33204 KB Output is correct
13 Correct 181 ms 38636 KB Output is correct
14 Correct 184 ms 39020 KB Output is correct
15 Runtime error 228 ms 97644 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -