답안 #467694

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
467694	2021-08-24T04:33:36 Z	jli12345	원숭이와 사과 나무 (IZhO12_apple)	C++14	0 / 100	58 ms	100548 KB

apple

#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, 1);
    while (Q--){
        int k; cin >> k;
        int a, b; cin >> a >> b;
        if (k == 1){
            int val = (b+C-(a+C)+1)-S(1, 1, 1000000000, a+C, b+C);
            cout << val << "\n";
            C += val;
        } else {
            U(1, 1, 1000000000, a+C, b+C, 0);
        }
    }
}

Subtask #1

0 / 100.0

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