Submission #482760

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
482760	2021-10-26T09:43:16 Z	CyberSleeper	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	374 ms	203408 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	113 ms	200700 KB	Output is correct
2	Correct	106 ms	200600 KB	Output is correct
3	Correct	117 ms	200656 KB	Output is correct
4	Correct	119 ms	200660 KB	Output is correct
5	Correct	118 ms	200712 KB	Output is correct
6	Correct	118 ms	200716 KB	Output is correct
7	Correct	120 ms	200744 KB	Output is correct
8	Correct	202 ms	200832 KB	Output is correct
9	Correct	301 ms	201092 KB	Output is correct
10	Correct	315 ms	200976 KB	Output is correct
11	Correct	307 ms	201016 KB	Output is correct
12	Correct	301 ms	201028 KB	Output is correct
13	Correct	276 ms	201156 KB	Output is correct
14	Correct	283 ms	201156 KB	Output is correct
15	Correct	373 ms	201516 KB	Output is correct
16	Correct	374 ms	203332 KB	Output is correct
17	Correct	283 ms	203408 KB	Output is correct
18	Correct	279 ms	203204 KB	Output is correct
19	Correct	363 ms	203332 KB	Output is correct
20	Correct	370 ms	203272 KB	Output is correct