답안 #667254

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
667254	2022-12-01T00:04:15 Z	divad	원숭이와 사과 나무 (IZhO12_apple)	C++14	0 / 100	550 ms	262144 KB

apple

/// aint dinamic / implicit
#include <iostream>
#define int long long
#define MAX 1000000000
using namespace std;
int m,t,x,y,sol,c;

struct nod{
    int st, dr;
    int sum;
    bool lazy;
    nod *fiu_st, *fiu_dr;

    nod(int x, int y){
        st = x;
        dr = y;
        sum = 0;
        lazy = false;
        fiu_st = fiu_dr = NULL;
    }
};

void propag(nod *&tata, nod *&fiu_st, nod *&fiu_dr, int st, int dr){
    if(st == dr){
        return ;
    }
    if(tata->lazy == false){
        /// nu e nevoie
        return ;
    }
    int mid = (st+dr)/2;
    if(fiu_st == NULL){
        fiu_st = new nod(st, mid);
    }
    if(fiu_dr == NULL){
        fiu_dr = new nod(mid+1, dr);
    }
    fiu_st->lazy = fiu_dr->lazy = true;
    tata->lazy = false;
    fiu_st->sum = (fiu_st->dr - fiu_st->st + 1);
    fiu_dr->sum = (fiu_dr->dr - fiu_dr->st + 1);
}

void query(nod *&tata, int st, int dr, int a, int b){
    if(tata == NULL){
        return ;
    }
    if(a <= st && dr <= b){
        sol += tata->sum;
    }else{
        int mid = (st+dr)/2;
        propag(tata, tata->fiu_st, tata->fiu_dr, st, dr);
        if(a <= mid){
            query(tata->fiu_st, st, mid, a, b);
        }
        if(b >= mid+1){
            query(tata->fiu_dr, mid+1, dr, a, b);
        }
    }
}
nod *aint;

void update(nod *&tata, int st, int dr, int a, int b){
    if(tata == NULL){
        tata = new nod(st, dr);
    }
    if(a <= st && dr <= b){
        tata->sum = dr-st+1;
        tata->lazy = true;
    }else{
        propag(tata, tata->fiu_st, tata->fiu_dr, st, dr);
        int mid = (st+dr)/2;
        if(a <= mid){
            update(tata->fiu_st, st, mid, a, b);
        }
        if(b >= mid+1){
            update(tata->fiu_dr, mid+1, dr, a, b);
        }
        int sum_st = 0, sum_dr = 0;
        if(tata->fiu_st != NULL){
            sum_st = tata->fiu_st->sum;
        }
        if(tata->fiu_dr != NULL){
            sum_dr = tata->fiu_dr->sum;
        }
        tata->sum = sum_st+sum_dr;
    }
}

signed main()
{
    aint = new nod(1, MAX);
    cin >> m;
    while(m--){
        cin >> t >> x >> y;
        x += c; y += c;
        if(t == 1){
            sol = 0;
            query(aint, 1, MAX, x, y);
            cout << sol << "\n";
            c = sol;
        }else{
            update(aint, 1, MAX, x, y);
        }
    }
    return 0;
}

Subtask #1

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	300 KB	Output is correct
4	Correct	24 ms	6416 KB	Output is correct
5	Correct	32 ms	7880 KB	Output is correct
6	Correct	27 ms	7500 KB	Output is correct
7	Correct	30 ms	7772 KB	Output is correct
8	Correct	183 ms	58956 KB	Output is correct
9	Correct	391 ms	102376 KB	Output is correct
10	Correct	384 ms	112980 KB	Output is correct
11	Correct	404 ms	121360 KB	Output is correct
12	Correct	432 ms	125124 KB	Output is correct
13	Correct	386 ms	145728 KB	Output is correct
14	Correct	374 ms	147028 KB	Output is correct
15	Runtime error	550 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-