oj.uz

답안 #478957

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
478957 2021-10-09T08:29:23 Z MohammadAghil 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
 452 ms 207624 KB 
#include <bits/stdc++.h> 
using  namespace std;
typedef  long long ll;
typedef  pair<int, int> pp;
#define  rep(i,l,r) for(int i = (l); i < r; i++)
#define  per(i,r,l) for(int i = (r); i >= l; i--)
#define  all(x) x.begin(), x.end()
#define  sz(x) (int)(x).size()
#define  pb push_back
#define  ff first
#define  ss second 
 
const ll mod = 998244353, maxn = 2e6 + 5, inf = 1e9 + 5;

struct Node{
    Node *l, *r;
    int lx, rx;
    int sum, lazy;
    Node(int lx, int rx): lx(lx), rx(rx){
        sum = 0, lazy = 0;
        l = r = NULL;
    }
} *root;

void pull(Node *x){
    x->lazy = 1;
    x->sum = x->rx - x->lx;
}

void shift(Node *x){
    int mid = (x->lx + x->rx) >> 1;
    if(!x->l) {
        x->l = new Node(x->lx, mid);
    }
    if(!x->r) x->r = new Node(mid, x->rx);
    if(x->lazy){
        pull(x->l); 
        pull(x->r);
    }
    x->lazy = 0;
}

void upd(int l, int r, Node *x = root){
    if(l <= x->lx && r >= x->rx){
        pull(x);
        return;
    }
    if(l >= x->rx || r <= x->lx) return;
    shift(x);
    upd(l, r, x->l);
    upd(l, r, x->r);
    x->sum = x->l->sum + x->r->sum;
}

int query(int l, int r, Node *x = root){
    if(l <= x->lx && r >= x->rx) return x->sum;
    if(l >= x->rx || r <= x->lx) return 0;
    shift(x);
    return query(l, r, x->l) + query(l, r, x->r); 
}

int main(){
    cin.tie(0) -> sync_with_stdio(0);
    root = new Node(0, inf);
    int q; cin >> q;
    int c = 0;
    while(q--){
        int d, l, r; cin >> d >> l >> r;
        if(d == 1){
            c = query(c + l, c + r + 1);
            cout << c << '\n';
        }else upd(c + l, c + r + 1);
    }
    return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 16 ms 4964 KB Output is correct
5 Correct 17 ms 5948 KB Output is correct
6 Correct 20 ms 5800 KB Output is correct
7 Correct 17 ms 5972 KB Output is correct
8 Correct 146 ms 44440 KB Output is correct
9 Correct 291 ms 77212 KB Output is correct
10 Correct 302 ms 85316 KB Output is correct
11 Correct 297 ms 91680 KB Output is correct
12 Correct 296 ms 94396 KB Output is correct
13 Correct 257 ms 109920 KB Output is correct
14 Correct 261 ms 111004 KB Output is correct
15 Correct 451 ms 201700 KB Output is correct
16 Correct 452 ms 203252 KB Output is correct
17 Correct 288 ms 114756 KB Output is correct
18 Correct 276 ms 114840 KB Output is correct
19 Correct 442 ms 207624 KB Output is correct
20 Correct 450 ms 207536 KB Output is correct