답안 #658117

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
658117	2022-11-12T07:58:19 Z	indigosquirrel	원숭이와 사과 나무 (IZhO12_apple)	C++14	100 / 100	531 ms	200144 KB

apple

#include <iostream>
#include <string>
#include <math.h>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <limits>
#include <queue>
#include <list>
#include <cstring>
#include <assert.h>

using namespace std;

const long long BAD = -1;

struct node {
    int v, p, l, r;
    int tl, tr;
    node(int tl, int tr, int l, int r, int v, int p) {
        this->v = v;
        this->p = p;
        this->tl = tl;
        this->tr = tr;
        this->l = l;
        this->r = r;
    }
};

struct Seg {

    vector<node> seg;
    int cnt = 0;

    Seg(long long n, long long maxi) {
        seg.push_back(node(BAD, BAD, 1, maxi, 0, BAD));
        cnt++;
    }

    void prop(int ind) {
        long long mid = (seg[ind].l + seg[ind].r) / 2;
        if (seg[ind].tl == BAD) {
            seg.push_back(node(BAD, BAD, seg[ind].l, mid, 0, BAD));
            seg[ind].tl = cnt++;
        }
        if (seg[ind].tr == BAD) {
            seg.push_back(node(BAD, BAD, mid + 1, seg[ind].r, 0, BAD));
            seg[ind].tr = cnt++;
        }
        node cur = seg[ind];
        if (cur.p != BAD) {
            seg[cur.tl].v = (seg[cur.tl].r - seg[cur.tl].l + 1) * cur.p;
            seg[cur.tl].p = cur.p;
            seg[cur.tr].v = (seg[cur.tr].r - seg[cur.tr].l + 1) * cur.p;
            seg[cur.tr].p = cur.p;
        }
        cur.p = BAD;
    }

    void set(int cur, long long l, long long r, long long v) {
        long long tl = seg[cur].l;
        long long tr = seg[cur].r;
        if (l > tr || r < tl) return;
        if (l <= tl && r >= tr) {
            seg[cur].v = (seg[cur].r - seg[cur].l + 1) * v;
            seg[cur].p = v;
            return;
        }
        prop(cur);
        long long mid = (seg[cur].l + seg[cur].r) / 2;
        set(seg[cur].tl, l, r, v);
        set(seg[cur].tr, l, r, v);
        //cout << "WHAT " << cur << " " << seg[cur].tl << " " << seg[cur].tr << endl;
        seg[cur].v = seg[seg[cur].tl].v + seg[seg[cur].tr].v;
    }

    long long query(int cur, long long l, long long r) {
        long long tl = seg[cur].l;
        long long tr = seg[cur].r;
        if (l > tr || r < tl) return 0;
        if (l <= tl && r >= tr) {
            return seg[cur].v;
        }
        prop(cur);
        long long res = 0;
        res += query(seg[cur].tl, l, r);
        res += query(seg[cur].tr, l, r);
        return res;
    }
};

int main() {
    int n;
    cin >> n;
    set<int> vals;
    long long maxi = 1e9;
    Seg seg(30 * 100000, maxi);
    long long c = 0;
    
    for (int i = 0; i < n; i++) {
        long long d, x, y;
        cin >> d >> x >> y;
        x += c;
        y += c;
        //cout << " WHAT " << c << " " << x << " " << c + y << endl;
        if (d == 1) {
            long long tot = seg.query(0, x, y);
            cout << tot << endl;
            c = tot;
        } else {
            seg.set(0, x, y, 1);
        }
    }
}

Compilation message

apple.cpp: In member function 'void Seg::set(int, long long int, long long int, long long int)':
apple.cpp:75:19: warning: unused variable 'mid' [-Wunused-variable]
   75 |         long long mid = (seg[cur].l + seg[cur].r) / 2;
      |                   ^~~

Subtask #1

100.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	212 KB	Output is correct
4	Correct	23 ms	3616 KB	Output is correct
5	Correct	25 ms	3660 KB	Output is correct
6	Correct	25 ms	3584 KB	Output is correct
7	Correct	25 ms	3660 KB	Output is correct
8	Correct	158 ms	25520 KB	Output is correct
9	Correct	327 ms	50688 KB	Output is correct
10	Correct	345 ms	50564 KB	Output is correct
11	Correct	342 ms	50696 KB	Output is correct
12	Correct	340 ms	50524 KB	Output is correct
13	Correct	352 ms	100412 KB	Output is correct
14	Correct	350 ms	100020 KB	Output is correct
15	Correct	531 ms	199996 KB	Output is correct
16	Correct	483 ms	200000 KB	Output is correct
17	Correct	365 ms	101344 KB	Output is correct
18	Correct	346 ms	101288 KB	Output is correct
19	Correct	490 ms	200016 KB	Output is correct
20	Correct	472 ms	200144 KB	Output is correct