Submission #1130580

#TimeUsernameProblemLanguageResultExecution timeMemory
1130580yusuf12360Monkey and Apple-trees (IZhO12_apple)C++20
100 / 100
400 ms205684 KiB
#include<bits/stdc++.h>
#define ld long double
#define pii pair<int, int>
#define vi vector<int>
#define vvi vector<vi> 
#define pb push_back
#define fi first
#define se second
#define TII tuple<int, int, int>
#define ts to_string
#pragma gcc optimize("O3");
using namespace std;
const int INF=1e9;
struct node{
    int l, r, sum=0, lazy=0;
    node *left=nullptr, *right=nullptr;
    node(int l, int r) : l(l), r(r) {}

    void extend() {
        if(l==r) return;
        int mid=l+r>>1;
        if(!left) left=new node(l, mid);
        if(!right) right=new node(mid+1, r);
    }
    void push() {
        if(l==r) return;
        extend();
        if(lazy) {
            left->lazy=1;
            left->sum=left->r-left->l+1;
            right->lazy=1;
            right->sum=right->r-right->l+1;
            lazy=0;
        }
    }
    void update(int ql, int qr) {
        if(max(l, ql)>min(r, qr)) return;
        if(ql<=l && r<=qr) {lazy=1; sum=r-l+1; return;}
        push();
        left->update(ql, qr);
        right->update(ql, qr);
        sum=left->sum+right->sum;
    }
    int get(int ql, int qr) {
        if(max(l, ql)>min(r, qr)) return 0;
        if(ql<=l && r<=qr) return sum;
        push();
        return left->get(ql, qr)+right->get(ql, qr);
    }
};
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int m, c=0; cin >> m;
    node *root = new node(1, INF);
    while(m--) {
        int type, ql, qr;
        cin >> type >> ql >> qr;
        if(type==1) c=root->get(ql+c, qr+c), cout << c << '\n';
        else root->update(ql+c, qr+c);
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...