Submission #478061

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
478061	2021-10-05T12:51:11 Z	CyberSleeper	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	413 ms	202476 KB

apple

#include <bits/stdc++.h>
#define fastio      ios_base::sync_with_stdio(false); cin.tie(NULL)
#define debug(x)    cout << "Line " << __LINE__ << ", " << #x << " is " << x << endl
#define BP(x)       __builtin_popcount(x)
#define fi          first
#define se          second
#define mp          make_pair
#define pb          push_back
//#define ll          long long
#define ull         unsigned long long
#define ld          long double
#define pld         pair<ld, ld>
#define pli         pair<ld, ll>
#define pii         pair<ll, ll>
#define pis         pair<ll, string>
#define pl          pair<ll, ll>
#define arri5        array<ll, 5>
#define nl          '\n'
#define sp          ' '
using namespace std;

const int MX=100007, MOD=1e9+7, INF=1e9+7;

int M, A[MX], sz=1;

struct SegTree{
    #define mi      (le+ri)/2
    #define idxl    ST[idx].ll
    #define idxr    ST[idx].rr

    struct Node{
        int sum, lz, ll, rr;
        Node(){
            sum=lz=0;
            ll=rr=-1;
        }
    }id;
    Node ST[128*MX];
    int letar, ritar;

    void ass(int idx){
        if(idxl==-1)
            idxl=sz++;
        if(idxr==-1)
            idxr=sz++;
    }
    void prop(int idx, int le, int ri){
        if(ST[idx].lz){
            ST[idx].sum=(ri-le+1);
            if(le<ri){
                ass(idx);
                ST[idxl].lz=ST[idxr].lz=1;
            }
            ST[idx].lz=0;
        }
    }
    void upd(int idx, int le, int ri){
        prop(idx, le, ri);
        if(ri<letar || ritar<le)
            return;
        if(letar<=le && ri<=ritar){
            ST[idx].lz++;
            prop(idx, le, ri);
            return;
        }
        ass(idx);
        upd(idxl, le, mi); upd(idxr, mi+1, ri);
        ST[idx].sum=ST[idxl].sum+ST[idxr].sum;
    }
    int que(int idx, int le, int ri){
        prop(idx, le, ri);
        if(ri<letar || ritar<le)
            return 0;
        if(letar<=le && ri<=ritar)
            return ST[idx].sum;
        ass(idx);
        return que(idxl, le, mi)+que(idxr, mi+1, ri);
    }

    void update(int le, int ri){
        letar=le, ritar=ri;
        upd(0, 0, INF);
    }
    int query(int le, int ri){
        letar=le, ritar=ri;
        return que(0, 0, INF);
    }
};

int main(){
    fastio;
    cin >> M;
    int C=0;
    SegTree ST;
    for(int ch, l, r; M--;){
        cin >> ch >> l >> r;
        l+=C;
        r+=C;
        if(ch&1){
            C=ST.query(l, r);
            cout << C << nl;
        }else{
            ST.update(l, r);
        }
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	113 ms	200644 KB	Output is correct
2	Correct	116 ms	200680 KB	Output is correct
3	Correct	113 ms	200676 KB	Output is correct
4	Correct	119 ms	200748 KB	Output is correct
5	Correct	130 ms	200840 KB	Output is correct
6	Correct	133 ms	200812 KB	Output is correct
7	Correct	124 ms	200900 KB	Output is correct
8	Correct	228 ms	201668 KB	Output is correct
9	Correct	343 ms	202232 KB	Output is correct
10	Correct	346 ms	202212 KB	Output is correct
11	Correct	344 ms	202324 KB	Output is correct
12	Correct	349 ms	202336 KB	Output is correct
13	Correct	331 ms	202476 KB	Output is correct
14	Correct	311 ms	202364 KB	Output is correct
15	Correct	396 ms	202308 KB	Output is correct
16	Correct	408 ms	202436 KB	Output is correct
17	Correct	329 ms	202364 KB	Output is correct
18	Correct	326 ms	202352 KB	Output is correct
19	Correct	411 ms	202352 KB	Output is correct
20	Correct	413 ms	202312 KB	Output is correct