답안 #658104

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
658104	2022-11-12T07:39:14 Z	indigosquirrel	원숭이와 사과 나무 (IZhO12_apple)	C++14	0 / 100	431 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(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	52 ms	141136 KB	Output is correct
2	Correct	51 ms	141180 KB	Output is correct
3	Correct	51 ms	141160 KB	Output is correct
4	Correct	71 ms	141308 KB	Output is correct
5	Correct	73 ms	141204 KB	Output is correct
6	Correct	80 ms	141172 KB	Output is correct
7	Correct	93 ms	141228 KB	Output is correct
8	Correct	197 ms	141364 KB	Output is correct
9	Correct	368 ms	141632 KB	Output is correct
10	Correct	357 ms	142076 KB	Output is correct
11	Correct	365 ms	142028 KB	Output is correct
12	Correct	360 ms	142076 KB	Output is correct
13	Correct	343 ms	142200 KB	Output is correct
14	Correct	338 ms	142112 KB	Output is correct
15	Runtime error	431 ms	262144 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-