Submission #468339

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
468339	2021-08-27T18:12:22 Z	jenishmonpara	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	425 ms	262148 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;
        }
        if(seg[i].lson == 0){
                return 0;
        }
        
        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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 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	19 ms	8696 KB	Output is correct
5	Correct	23 ms	8640 KB	Output is correct
6	Correct	23 ms	8600 KB	Output is correct
7	Correct	22 ms	8648 KB	Output is correct
8	Correct	182 ms	66128 KB	Output is correct
9	Correct	376 ms	132040 KB	Output is correct
10	Correct	373 ms	131988 KB	Output is correct
11	Correct	400 ms	131888 KB	Output is correct
12	Correct	411 ms	131900 KB	Output is correct
13	Runtime error	425 ms	262148 KB	Execution killed with signal 9
14	Halted	0 ms	0 KB	-