Submission #468341

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
468341	2021-08-27T18:18:00 Z	jenishmonpara	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	506 ms	134372 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

100.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	16 ms	4548 KB	Output is correct
5	Correct	19 ms	4496 KB	Output is correct
6	Correct	19 ms	4548 KB	Output is correct
7	Correct	19 ms	4544 KB	Output is correct
8	Correct	140 ms	33288 KB	Output is correct
9	Correct	294 ms	66412 KB	Output is correct
10	Correct	298 ms	66292 KB	Output is correct
11	Correct	312 ms	66312 KB	Output is correct
12	Correct	319 ms	66240 KB	Output is correct
13	Correct	322 ms	134236 KB	Output is correct
14	Correct	322 ms	134372 KB	Output is correct
15	Correct	441 ms	133172 KB	Output is correct
16	Correct	506 ms	133340 KB	Output is correct
17	Correct	323 ms	134280 KB	Output is correct
18	Correct	322 ms	134200 KB	Output is correct
19	Correct	447 ms	133088 KB	Output is correct
20	Correct	438 ms	133148 KB	Output is correct