Submission #38736

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
38736	2018-01-06T10:52:57 Z	daniel_02	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	816 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 m;
int cnt = 2,c;
int ty, l, r;

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 ++;

        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 (tl > tr || 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 (tl > tr || 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()
{
    cin >> m;

    while (m--)
    {
        scanf("%d", &ty);
        scanf("%d%d", &l, &r);

        l += c;
        r += c;

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

Compilation message

apple.cpp:100:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
apple.cpp: In function 'int main()':
apple.cpp:106:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &ty);
                         ^
apple.cpp:107: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	26 ms	122328 KB	Output is correct
2	Correct	23 ms	122328 KB	Output is correct
3	Correct	26 ms	122328 KB	Output is correct
4	Correct	43 ms	122328 KB	Output is correct
5	Correct	59 ms	122328 KB	Output is correct
6	Correct	63 ms	122328 KB	Output is correct
7	Correct	76 ms	122328 KB	Output is correct
8	Correct	469 ms	122328 KB	Output is correct
9	Correct	816 ms	122328 KB	Output is correct
10	Runtime error	686 ms	122328 KB	Execution timed out (wall clock limit exceeded)
11	Halted	0 ms	0 KB	-