Submission #468340

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
468340	2021-08-27T18:16:12 Z	jenishmonpara	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	439 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;
        }
        
        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,-2e9,2e9,c+l,c+r);
                        cout<<c;nl;
                }
                else{
                        upd(1,-2e9,2e9,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	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	19 ms	8640 KB	Output is correct
5	Correct	23 ms	8692 KB	Output is correct
6	Correct	23 ms	8708 KB	Output is correct
7	Correct	24 ms	8608 KB	Output is correct
8	Correct	183 ms	66152 KB	Output is correct
9	Correct	373 ms	131972 KB	Output is correct
10	Correct	387 ms	131884 KB	Output is correct
11	Correct	439 ms	131880 KB	Output is correct
12	Correct	406 ms	131880 KB	Output is correct
13	Runtime error	423 ms	262148 KB	Execution killed with signal 9
14	Halted	0 ms	0 KB	-