oj.uz

답안 #467695

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
467695 2021-08-24T04:55:38 Z jli12345 원숭이와 사과 나무 (IZhO12_apple) C++14
0 / 100
 57 ms 100608 KB 
#include <bits/stdc++.h>
using namespace std;

void fastIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
}

struct Node{
    int lson, rson;
    int sum;
    int settag;
    Node(){
        lson = rson = -1;
        sum = 1;
        settag = -1;
    }
} st[64*100100];

int nodecnt = 1;

void pushdown(int node, int l, int mid, int r){
    if (st[node].lson == -1)
        st[node].lson = ++nodecnt;
    if (st[node].rson == -1)
        st[node].rson = ++nodecnt;
    if (st[node].settag == -1)
        return;
    st[st[node].lson].sum = (mid-l+1)*st[node].settag;
    st[st[node].rson].sum = (r-mid)*st[node].settag;
    st[st[node].lson].settag = st[st[node].rson].settag = st[node].settag;
    st[node].settag = -1;
}

void U(int node, int l, int r, int tl, int tr, int val){
    if (l > tr || r < tl)
        return;
    if (l >= tl && r <= tr){
        st[node].sum = (r-l+1)*val;
        st[node].settag = val;
        return;
    }
    int mid = (l+r)/2;
    pushdown(node, l, mid, r);
    U(st[node].lson, l, mid, tl, tr, val);
    U(st[node].rson, mid+1, r, tl, tr, val);
    st[node].sum = st[st[node].lson].sum+st[st[node].rson].sum;
}

int S(int node, int l, int r, int tl, int tr){
    if (l > tr || r < tl)
        return 0;
    if (l >= tl && r <= tr){
        return st[node].sum;
    }
    int mid = (l+r)/2;
    pushdown(node, l, mid, r);
    return S(st[node].lson, l, mid, tl, tr)+S(st[node].rson, mid+1, r, tl, tr);
}

int main(){
    fastIO();
    int Q; cin >> Q;
    int C = 0;
    U(1, 1, 1000000000, 1, 1000000000, 0);
    while (Q--){
        int k; cin >> k;
        int a, b; cin >> a >> b;
        if (k == 1){
            int val = S(1, 1, 1000000000, a+C, b+C);
            cout << val << "\n";
            C += val;
        } else {
            U(1, 1, 1000000000, a+C, b+C, 1);
        }
    }
}

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 100608 KB Output is correct
2 Incorrect 55 ms 100548 KB Output isn't correct
3 Halted 0 ms 0 KB -