Submission #106561

#	Time	Username	Problem	Language	Result	Execution time	Memory
106561		Hideo	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	558 ms	159768 KiB

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 (stderr)

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 / 100