Submission #106561

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
106561	2019-04-19T04:42:38 Z	Hideo	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	558 ms	159768 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 = 1e5 + 7;
const int INF = 1e9;

int n, c, x;

struct ST{
    int l, r, s, val;
    ST(){
        l = r = s = val = 0;
    }
};
ST t[100 * 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

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	141 ms	156920 KB	Output is correct
2	Correct	139 ms	156984 KB	Output is correct
3	Correct	126 ms	156892 KB	Output is correct
4	Correct	135 ms	156920 KB	Output is correct
5	Correct	164 ms	157008 KB	Output is correct
6	Correct	148 ms	156920 KB	Output is correct
7	Correct	137 ms	156920 KB	Output is correct
8	Correct	282 ms	157048 KB	Output is correct
9	Correct	457 ms	157432 KB	Output is correct
10	Correct	467 ms	157560 KB	Output is correct
11	Correct	444 ms	157444 KB	Output is correct
12	Correct	489 ms	157504 KB	Output is correct
13	Correct	425 ms	157584 KB	Output is correct
14	Correct	416 ms	159480 KB	Output is correct
15	Correct	551 ms	159768 KB	Output is correct
16	Correct	544 ms	159736 KB	Output is correct
17	Correct	415 ms	159532 KB	Output is correct
18	Correct	480 ms	159608 KB	Output is correct
19	Correct	518 ms	159608 KB	Output is correct
20	Correct	558 ms	159736 KB	Output is correct