답안 #658116

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
658116	2022-11-12T07:56:11 Z	indigosquirrel	원숭이와 사과 나무 (IZhO12_apple)	C++14	0 / 100	625 ms	262144 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 = -1e18;

struct node {
    long long v, p, l, r;
    long long tl, tr;
    node(long long tl, long long tr, long long l, long long r, long long v, long long 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

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	26 ms	6596 KB	Output is correct
5	Correct	32 ms	6496 KB	Output is correct
6	Correct	31 ms	6600 KB	Output is correct
7	Correct	32 ms	6600 KB	Output is correct
8	Correct	218 ms	49720 KB	Output is correct
9	Correct	400 ms	99116 KB	Output is correct
10	Correct	435 ms	99148 KB	Output is correct
11	Correct	450 ms	99088 KB	Output is correct
12	Correct	433 ms	99080 KB	Output is correct
13	Correct	472 ms	197820 KB	Output is correct
14	Correct	437 ms	197752 KB	Output is correct
15	Runtime error	625 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-