Submission #38732

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
38732	2018-01-06T10:48:18 Z	daniel_02	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	783 ms	122328 KB

apple

#include <bits/stdc++.h>

#define ll long long
#define OK cout << "OK" << endl;

using namespace std;

const int N = 7e6 + 7e5;
const int inf = 1e9 + 7;

struct node
{
    int sum, l, r,add;
    node()
    {
        sum = l = r = add = 0;
    }
}t[N];

int cnt = 2;
int c;

void push (int v, int tl, int tr) {
    if (t[v].add != 0) {
        if (!t[v].l)
            t[v].l = cnt ++;
        if  (!t[v].r)
            t[v].r = cnt ++;
        if (cnt > N - 5) {
        while (1) {

        }
    }
        t[t[v].l].add = 1;
        t[t[v].r].add = 1;
        t[v].sum = (tr - tl + 1);
        t[v].add = 0;
    }
}

void update(int v, int tl, int tr, int l, int r)
{
    if (cnt > N - 5) {
        while (1) {

        }
    }
    if (tr < l || tl > r)
    {
        return;
    }
    push (v, tl, tr);

    if (tl >= l && r >= tr)
    {
        t[v].add = 1;
    }
    else
    {
        int mid = (tl + tr) >> 1;

        if (!t[v].l)
        {
            t[v].l = cnt++;
        }
        update(t[v].l, tl, mid, l, r);

        if (!t[v].r)
        {
            t[v].r = cnt++;
        }
        update(t[v].r, mid + 1, tr, l, r);

        push (v, tl, tr);
        push (t[v].l, tl, mid);
        push (t[v].r, mid + 1, tr);

        t[v].sum = t[t[v].l].sum + t[t[v].r].sum;
    }
}
int get(int v, int tl, int tr, int l, int r)
{
    if (cnt > N - 5) {
        while (1) {

        }
    }
    if (tl > r || l > tr)
    {
        return 0;
    }

    push (v, tl, tr);

    if (tl >= l && r >= tr)
    {
        return t[v].sum;
    }
    else
    {
        int mid = (tl + tr) >> 1;

        int s1 = 0, s2 = 0;

        if (t[v].l)
        {
            s1 = get(t[v].l, tl, mid, l, r);
        }
        if (t[v].r)
        {
            s2 = get(t[v].r, mid + 1, tr, l, r);
        }

        return (s1 + s2);
    }
}
main()
{
    int m;

    cin >> m;

    while (m--)
    {
        int ty, l, r;

        scanf("%d", &ty);
        scanf("%d%d", &l, &r);

        l += c;
        r += c;

        if (ty == 1)
        {
            int ans;
            ans = get(1, 1, inf, l, r);
            cout << ans << endl;
            c = ans;
        }
        else
        {
            update(1, 1, inf, l, r);
        }
    }
}

Compilation message

apple.cpp:117:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
apple.cpp: In function 'int main()':
apple.cpp:127:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &ty);
                         ^
apple.cpp:128:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &l, &r);
                              ^

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	122328 KB	Output is correct
2	Correct	9 ms	122328 KB	Output is correct
3	Correct	16 ms	122328 KB	Output is correct
4	Correct	59 ms	122328 KB	Output is correct
5	Correct	99 ms	122328 KB	Output is correct
6	Correct	83 ms	122328 KB	Output is correct
7	Correct	66 ms	122328 KB	Output is correct
8	Correct	259 ms	122328 KB	Output is correct
9	Correct	719 ms	122328 KB	Output is correct
10	Runtime error	783 ms	122328 KB	Execution timed out (wall clock limit exceeded)
11	Halted	0 ms	0 KB	-