Submission #478064

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
478064	2021-10-05T12:56:04 Z	CyberSleeper	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	415 ms	201284 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].lc
    #define idxr    ST[idx].rc

    struct Node{
        int sum, lz, lc, rc;
        Node(){
            sum=lz=0;
            lc=rc=-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	112 ms	200816 KB	Output is correct
2	Correct	109 ms	200644 KB	Output is correct
3	Correct	124 ms	200808 KB	Output is correct
4	Correct	130 ms	200664 KB	Output is correct
5	Correct	126 ms	200700 KB	Output is correct
6	Correct	130 ms	200700 KB	Output is correct
7	Correct	122 ms	200644 KB	Output is correct
8	Correct	218 ms	200848 KB	Output is correct
9	Correct	343 ms	201264 KB	Output is correct
10	Correct	344 ms	201212 KB	Output is correct
11	Correct	355 ms	201104 KB	Output is correct
12	Correct	339 ms	201068 KB	Output is correct
13	Correct	319 ms	201080 KB	Output is correct
14	Correct	323 ms	201084 KB	Output is correct
15	Correct	408 ms	201124 KB	Output is correct
16	Correct	415 ms	201284 KB	Output is correct
17	Correct	351 ms	201156 KB	Output is correct
18	Correct	333 ms	201180 KB	Output is correct
19	Correct	413 ms	201172 KB	Output is correct
20	Correct	414 ms	201208 KB	Output is correct