Submission #658116

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
658116	2022-11-12T07:56:11 Z	indigosquirrel	Monkey and Apple-trees (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

#	Verdict	Execution time	Memory	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	-