Submission #482759

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
482759	2021-10-26T09:42:45 Z	CyberSleeper	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	290 ms	102976 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[64*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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	55 ms	100456 KB	Output is correct
2	Correct	59 ms	100584 KB	Output is correct
3	Correct	58 ms	100424 KB	Output is correct
4	Correct	77 ms	100412 KB	Output is correct
5	Correct	68 ms	100508 KB	Output is correct
6	Correct	67 ms	100428 KB	Output is correct
7	Correct	66 ms	100484 KB	Output is correct
8	Correct	151 ms	100664 KB	Output is correct
9	Correct	251 ms	100824 KB	Output is correct
10	Correct	272 ms	100876 KB	Output is correct
11	Correct	274 ms	100948 KB	Output is correct
12	Correct	290 ms	102556 KB	Output is correct
13	Correct	237 ms	102976 KB	Output is correct
14	Correct	262 ms	102948 KB	Output is correct
15	Runtime error	274 ms	102852 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-