Submission #32054

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
32054	2017-09-23T13:30:21 Z	mateuscgc	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	136 ms	2176 KB

apple

// https://oj.uz/problem/view/IZhO12_apple

#include <bits/stdc++.h>

using namespace std;
#define endl "\n";

struct node {
    int red;
    node *esq, *dir;
    node() {
        red = 0, esq = 0, dir = 0;
    }
};

const int MAXN = 1e9 + 10; // CHANGE THIS BITCH!!!

void update(node *no, int l, int r, int i, int j) { // Range update
    if(l == i && r == j) {
        no->red = r-l+1;
    } else if(no->red < r-l+1){
        if(!(no->esq)) no->esq = new node();
        if(!(no->dir)) no->dir = new node();
        int mid = (l+r)/2;
        if(j <= mid) update(no->esq, l, mid, i, j);
        else if(i > mid) update(no->dir, mid+1, r, i, j);
        else {
            update(no->esq, l, mid, i, mid);
            update(no->dir, mid+1, r, mid+1, j);
        }

        no->red = no->esq->red + no->dir->red;
    }
}

int query(node *no, int l, int r, int i, int j) {
    if(no->red == 0) return 0;
    if(no->red == r-l+1) return j-i+1;
    
    if(!(no->esq)) no->esq = new node();
    if(!(no->dir)) no->dir = new node();
    int mid = (l+r)/2;
    if(j <= mid) return query(no->esq, l, mid, i, j);
    else if(i > mid) return query(no->dir, mid+1, r, i, j);
    else return query(no->esq, l, mid, i, mid) +
                query(no->dir, mid+1, r, mid+1, j);
}

int main() {
    ios_base::sync_with_stdio(false);
    int m;
    cin >> m;

    node *root = new node();

    int c = 0;
    for(int i = 0; i < m; i++) {
        int d, a, b;
        cin >> d >> a >> b;
        if(d == 1) {
            int red = query(root, 0, MAXN-1, a+c-1, b+c-1);
            cout << red << endl;
            c = red;
        } else {
            update(root, 0, MAXN-1, a+c-1, b+c-1);
        }
    }
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2176 KB	Output is correct
2	Correct	0 ms	2176 KB	Output is correct
3	Correct	0 ms	2176 KB	Output is correct
4	Correct	16 ms	2176 KB	Output is correct
5	Correct	6 ms	2176 KB	Output is correct
6	Correct	9 ms	2176 KB	Output is correct
7	Correct	13 ms	2176 KB	Output is correct
8	Correct	33 ms	2176 KB	Output is correct
9	Correct	136 ms	2176 KB	Output is correct
10	Runtime error	123 ms	2176 KB	Execution timed out (wall clock limit exceeded)
11	Halted	0 ms	0 KB	-