Submission #468136

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
468136	2021-08-26T20:52:10 Z	jenishmonpara	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	1 ms	332 KB

apple

#include <bits/stdc++.h>
using namespace std;
long double PI = acos(-1);
long double DEL = 1e-12;
long long M =  1e9 + 7;
const long long N = 3e5 + 10;
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#define ftt cin>>tc;for(int cas=1;cas<=tc;++cas)
#define all(a) a.begin(),a.end()
#define sq(a) ((a)*(a))
#define double long double
#define dbg cout<<"\nhi\n";
#define int long long
#define nl cout<<"\n"
#define sp <<" "<<
#define mid ((l+r)>>1)
#define X real()
#define Y imag()


//*********************************** CHECK CONSTRAINTS ***********************************
int cnt, sum, mx, mn, ans, a[N], b[N];
int n, m, d, i, j, k, l, p, q, r, t, w, x, y, z, tc;
string s;



//************************************* CODE STARTS ****************************************

struct node{
        int lson,rson,s,lz;
        node(){
                lson = rson = lz = s = 0;
        }
};

vector<node> seg;

void push(int i,int l,int r){
        if(seg[i].lz == 0){
                return;
        }
        seg[i].s = r - l + 1;
        seg[i].lz = 0;
        if(l != r){
                if(!seg[i].lson){
                        seg[i].lson = seg.size();
                        seg.emplace_back();
                        seg[seg[i].lson].lz = 1;
                }
                if(!seg[i].rson){
                        seg[i].rson = seg.size();
                        seg.emplace_back();
                        seg[seg[i].rson].lz = 1;
                }
        }
//        cout<<"_______" sp i sp l sp r;nl;
}

int query(int i,int l,int r,int a,int b){
        if(l > b or r < a){
                return 0;
        }
        push(i,l,r);
        if(a <= l and r <= b){
                return seg[i].s;
        }
        if(!seg[i].lson){
                seg[i].lson = seg.size();
                seg.emplace_back();
        }
        if(!seg[i].rson){
                seg[i].rson = seg.size();
                seg.emplace_back();
        }
        
        int ret = query(seg[i].lson,l,mid,a,b) + query(seg[i].rson,mid+1,r,a,b);
//        cout<<i sp l sp r sp ret;nl;
        return ret;
}

void update(int i,int l,int r,int a,int b){
        push(i,l,r);

        if(l > b or r < a){
                return;
        }

        if(a <= l and r <= b){
                seg[i].lz = 1;
                push(i,l,r);
//                cout<<"--------" sp i sp l sp r sp a sp b sp seg[i].s;nl;
                return;
        }
        if(!seg[i].lson){
                seg[i].lson = seg.size();
                seg.emplace_back();
        }
        if(!seg[i].rson){
                seg[i].rson = seg.size();
                seg.emplace_back();
        }
        update(seg[i].lson,l,mid,a,b);
        update(seg[i].rson,mid+1,r,a,b);
        seg[i].s = seg[seg[i].lson].s + seg[seg[i].rson].s;
//        cout<<i sp l sp r sp seg[i].s sp seg[seg[i].lson].s sp seg[seg[i].rson].s sp seg[i].rson;nl;
}


int32_t main()
{
        ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
        seg.emplace_back();
        seg.emplace_back();
        int c = 0;
        ftt{
                cin>>t>>l>>r;
                if(t == 2){
                        update(1,1,1e9,l+c,r+c);
                }
                else{
                        c = query(1,1,1e9,l+c,r+c);
                        cout<<c;nl;
                }
        }
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Incorrect	1 ms	332 KB	Output isn't correct
4	Halted	0 ms	0 KB	-