Submission #468342

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
468342	2021-08-27T18:18:43 Z	jenishmonpara	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	467 ms	132220 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 s,lz,lson,rson;
        node() : s(0),lz(0),lson(0),rson(0){}
};

vector<node> seg;

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

void upd(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);
                return;
        }
        if(seg[i].lson == 0){
                seg[i].lson=seg.size();
                seg.emplace_back();
                seg[i].rson=seg.size();
                seg.emplace_back();
        }
        upd(seg[i].lson,l,mid,a,b);
        upd(seg[i].rson,mid+1,r,a,b);
        seg[i].s = seg[seg[i].lson].s + seg[seg[i].rson].s;
}

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

        if(l > b or r < a or seg[i].s == 0){
                return 0;
        }
        if(a <= l and r <= b){
                return seg[i].s;
        }
        
        return get(seg[i].lson,l,mid,a,b) + get(seg[i].rson,mid+1,r,a,b);

}

int32_t main()
{
        ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//#ifndef ONLINE_JUDGE
//        freopen("/Users/jenish/XCode/cp/input.txt","r",stdin);
//#endif
        seg.emplace_back();
        seg.emplace_back();
        int c = 0;
        ftt{
                cin >> x >> l >> r;
                if(x == 1){
                        c = get(1,1,1e9,c+l,c+r);
                        cout<<c;nl;
                }
                else{
                        upd(1,1,1e9,c+l,c+r);
                }
        }
}

Subtask #1

100.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	Correct	1 ms	204 KB	Output is correct
4	Correct	15 ms	4556 KB	Output is correct
5	Correct	19 ms	4536 KB	Output is correct
6	Correct	19 ms	4592 KB	Output is correct
7	Correct	19 ms	4512 KB	Output is correct
8	Correct	143 ms	33320 KB	Output is correct
9	Correct	287 ms	66364 KB	Output is correct
10	Correct	302 ms	66248 KB	Output is correct
11	Correct	302 ms	66288 KB	Output is correct
12	Correct	304 ms	66356 KB	Output is correct
13	Correct	319 ms	132192 KB	Output is correct
14	Correct	319 ms	132220 KB	Output is correct
15	Correct	430 ms	132012 KB	Output is correct
16	Correct	467 ms	131924 KB	Output is correct
17	Correct	314 ms	132124 KB	Output is correct
18	Correct	315 ms	132116 KB	Output is correct
19	Correct	441 ms	131880 KB	Output is correct
20	Correct	434 ms	131948 KB	Output is correct