oj.uz

Submission #639013

# Submission time Handle Problem Language Result Execution time Memory
639013 2022-09-08T09:04:20 Z zaneyu Monkey and Apple-trees (IZhO12_apple) C++14
100 / 100
 399 ms 174916 KB 
/*input
4
2 2 3
1 1 3
2 2 3
1 -1 3w
*/
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<long long,null_type,less_equal<long long>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
//order_of_key #of elements less than x
// find_by_order kth element
using ll=long long;
using ld=long double;
using pii=pair<int,int>;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()),c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET(v,x) lower_bound(ALL(v),x)-v.begin()
const int maxn=1e5+3;
const int INF=0x3f3f3f3f;
const int MOD=1e6+3;
const ld PI=acos(-1.0l);
const ld eps=1e-6;
const ll INF64=9e18+1;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
    out<<P.f<<' '<<P.s;
    return out;
}
template<typename T>
ostream& operator<<(ostream& out,vector<T> V){
    REP(i,sz(V)) out<<V[i]<<((i!=sz(V)-1)?" ":"");
    return out;
}
int mult(int a,int b){
    return 1LL*a*b%MOD;
}
ll mypow(ll a,ll b,ll mod){
    if(b<=0) return 1;
    a%=mod;
    ll res=1LL;
    while(b){
        if(b&1) res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}
struct node{
    ll sum=0,lazy=0;
    int lc=0,rc=0;
}seg[80*maxn];
//check this line
int tot=2;
inline void pushdown(int idx,int l,int r){
    if(!seg[idx].lazy) return;
    seg[idx].sum=r-l+1;
    if(l!=r){
        if(!seg[idx].lc) seg[idx].lc=(tot++);
        if(!seg[idx].rc) seg[idx].rc=(tot++);
        seg[seg[idx].lc].lazy=seg[idx].lazy;
        seg[seg[idx].rc].lazy=seg[idx].lazy;
    }
    seg[idx].lazy=0;
}
inline void mdf(int &idx,int l,int r,int ql,int qr,int x){
    if(!idx){
        idx=(tot++);
    }
    pushdown(idx,l,r);
    if(r<ql or l>qr) return;
    if(ql<=l and r<=qr){
        seg[idx].lazy=x;
        pushdown(idx,l,r);
        return;
    }
    int mid=(l+r)/2;
    mdf(seg[idx].lc,l,mid,ql,qr,x);
    mdf(seg[idx].rc,mid+1,r,ql,qr,x);
    seg[idx].sum=(seg[seg[idx].lc].sum+seg[seg[idx].rc].sum);
}
inline ll query(int &idx,int l,int r,int ql,int qr){
    if(r<ql or l>qr) return 0;
    if(!idx){
        idx=(tot++);
    }
    pushdown(idx,l,r);
    if(ql<=l and r<=qr){
        return seg[idx].sum;
    }
    int mid=(l+r)/2;
    return (query(seg[idx].lc,l,mid,ql,qr)+query(seg[idx].rc,mid+1,r,ql,qr));
}

int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int q;
    cin>>q;
    int c=0;
    int rt=1;
    int mx=1e9;
    while(q--){
        int d,x,y;
        cin>>d>>x>>y;
        x+=c,y+=c;
        if(d==2){
            mdf(rt,1,mx,x,y,1);
        }
        else{
            cout<<(c=query(rt,1,mx,x,y))<<'\n';
        }
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 13 ms 4100 KB Output is correct
5 Correct 17 ms 4936 KB Output is correct
6 Correct 17 ms 4736 KB Output is correct
7 Correct 16 ms 4948 KB Output is correct
8 Correct 115 ms 35692 KB Output is correct
9 Correct 265 ms 61356 KB Output is correct
10 Correct 278 ms 68436 KB Output is correct
11 Correct 263 ms 73820 KB Output is correct
12 Correct 294 ms 76416 KB Output is correct
13 Correct 233 ms 92716 KB Output is correct
14 Correct 268 ms 93892 KB Output is correct
15 Correct 363 ms 169676 KB Output is correct
16 Correct 399 ms 170932 KB Output is correct
17 Correct 248 ms 97164 KB Output is correct
18 Correct 265 ms 97124 KB Output is correct
19 Correct 365 ms 174836 KB Output is correct
20 Correct 394 ms 174916 KB Output is correct