답안 #658098

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
658098	2022-11-12T07:36:22 Z	indigosquirrel	원숭이와 사과 나무 (IZhO12_apple)	C++14	0 / 100	708 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.assign(n + 1, node(BAD, BAD, 1, n, 0, BAD));
        seg[cnt++] = node(BAD, BAD, 1, maxi, 0, BAD);
    }

    void prop(node & cur) {
        long long mid = (cur.l + cur.r) / 2;
        if (cur.tl == BAD) {
            seg[cnt] = node(BAD, BAD, cur.l, mid, 0, BAD);
            cur.tl = cnt++;
        }
        if (cur.tr == BAD) {
            seg[cnt] = node(BAD, BAD, mid + 1, cur.r, 0, BAD);
            cur.tr = cnt++;
        }
        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(seg[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(seg[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(40 * 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	71 ms	188072 KB	Output is correct
2	Correct	87 ms	188164 KB	Output is correct
3	Correct	78 ms	188176 KB	Output is correct
4	Correct	91 ms	188288 KB	Output is correct
5	Correct	107 ms	188232 KB	Output is correct
6	Correct	110 ms	188280 KB	Output is correct
7	Correct	97 ms	188352 KB	Output is correct
8	Correct	232 ms	189184 KB	Output is correct
9	Correct	420 ms	190216 KB	Output is correct
10	Correct	481 ms	190196 KB	Output is correct
11	Correct	428 ms	190312 KB	Output is correct
12	Correct	419 ms	190328 KB	Output is correct
13	Correct	382 ms	190624 KB	Output is correct
14	Correct	363 ms	190688 KB	Output is correct
15	Runtime error	708 ms	262144 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-