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
#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);
                              ^
# 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 -