Submission #106560

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
106560	2019-04-19T04:41:46 Z	Hideo	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	431 ms	128400 KB

apple

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define vi vector < int >
#define vl vector < ll >
#define pi pair < int, int >
#define pii pair < int, pi >
#define vii vector < pi >

const int N = 2e5 + 7;
const int INF = 1e9;

int n, c, x;

struct ST{
    int l, r, s, val;
    ST(){
        l = r = s = val = 0;
    }
};
ST t[20 * N];

void push (int v, int l, int r){
    if (l != r){
        if (!t[v].l)
            t[v].l = ++c;
        if (!t[v].r)
            t[v].r = ++c;
    }
    if (t[v].val){
        t[v].s = r - l + 1;
        t[t[v].l].val = t[t[v].r].val = 1;
    }
}

void upd (int v, int l, int r, int ql, int qr){
    push(v, l, r);
    if (ql <= l && r <= qr){
        t[v].val = 1;
        push(v, l, r);
        return;
    }
    if (r < ql || l > qr)
        return;
    int mid = (l + r) >> 1;
    upd(t[v].l, l, mid, ql, qr);
    upd(t[v].r, mid + 1, r, ql, qr);
    t[v].s = t[t[v].l].s + t[t[v].r].s;
}

int get (int v, int l, int r, int ql, int qr){
    push(v, l, r);
    if (ql <= l && r <= qr)
        return t[v].s;
    if (r < ql || l > qr)
        return 0;
    int mid = (l + r) >> 1;
    return get(t[v].l, l, mid, ql, qr) + get(t[v].r, mid + 1, r, ql, qr);
}
main(){
    c = 1;
    cin >> n;
    for (int i = 1; i <= n; i++){
        int t, l, r;
        scanf("%d%d%d", &t, &l, &r);
        if (t == 1){
            x = get(1, 1, INF, l + x, r + x);
            printf("%d\n", x);
        }
        else
            upd(1, 1, INF, l + x, r + x);
    }
}

Compilation message

apple.cpp:65:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
apple.cpp: In function 'int main()':
apple.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &t, &l, &r);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	58 ms	62968 KB	Output is correct
2	Correct	68 ms	62960 KB	Output is correct
3	Correct	61 ms	62968 KB	Output is correct
4	Correct	73 ms	62964 KB	Output is correct
5	Correct	69 ms	62968 KB	Output is correct
6	Correct	70 ms	62944 KB	Output is correct
7	Correct	69 ms	62968 KB	Output is correct
8	Correct	194 ms	63128 KB	Output is correct
9	Correct	373 ms	65116 KB	Output is correct
10	Correct	398 ms	65372 KB	Output is correct
11	Correct	425 ms	65324 KB	Output is correct
12	Correct	431 ms	65348 KB	Output is correct
13	Runtime error	381 ms	128400 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
14	Halted	0 ms	0 KB	-