Submission #38719

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
38719	2018-01-06T10:31:39 Z	daniel_02	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	819 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 ++;

        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 (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 = max(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 > 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:101:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
apple.cpp: In function 'int main()':
apple.cpp:111:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &ty);
                         ^
apple.cpp:112: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	16 ms	122328 KB	Output is correct
2	Correct	19 ms	122328 KB	Output is correct
3	Correct	33 ms	122328 KB	Output is correct
4	Correct	29 ms	122328 KB	Output is correct
5	Correct	83 ms	122328 KB	Output is correct
6	Correct	59 ms	122328 KB	Output is correct
7	Correct	79 ms	122328 KB	Output is correct
8	Correct	259 ms	122328 KB	Output is correct
9	Correct	793 ms	122328 KB	Output is correct
10	Correct	659 ms	122328 KB	Output is correct
11	Runtime error	819 ms	122328 KB	Execution timed out (wall clock limit exceeded)
12	Halted	0 ms	0 KB	-