Submission #658102

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
658102	2022-11-12T07:38:06 Z	indigosquirrel	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	207 ms	96364 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(10 * 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	19 ms	47188 KB	Output is correct
2	Correct	19 ms	47180 KB	Output is correct
3	Correct	19 ms	47212 KB	Output is correct
4	Correct	37 ms	47396 KB	Output is correct
5	Correct	41 ms	47448 KB	Output is correct
6	Correct	41 ms	47444 KB	Output is correct
7	Correct	44 ms	47376 KB	Output is correct
8	Correct	168 ms	47936 KB	Output is correct
9	Runtime error	207 ms	96364 KB	Execution killed with signal 11
10	Halted	0 ms	0 KB	-