Submission #38722

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
38722	2018-01-06T10:37:26 Z	daniel_02	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	833 ms	122344 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)1e3];

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 = 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:102:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
apple.cpp: In function 'int main()':
apple.cpp:112:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &ty);
                         ^
apple.cpp:113: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	122344 KB	Output is correct
2	Correct	23 ms	122344 KB	Output is correct
3	Correct	29 ms	122344 KB	Output is correct
4	Correct	83 ms	122344 KB	Output is correct
5	Correct	49 ms	122344 KB	Output is correct
6	Correct	59 ms	122344 KB	Output is correct
7	Correct	53 ms	122344 KB	Output is correct
8	Correct	429 ms	122344 KB	Output is correct
9	Correct	663 ms	122344 KB	Output is correct
10	Correct	619 ms	122344 KB	Output is correct
11	Correct	833 ms	122344 KB	Output is correct
12	Correct	719 ms	122344 KB	Output is correct
13	Correct	566 ms	122344 KB	Output is correct
14	Runtime error	526 ms	122344 KB	Execution timed out (wall clock limit exceeded)
15	Halted	0 ms	0 KB	-