oj.uz

Submission #312462

# Submission time Handle Problem Language Result Execution time Memory
312462 2020-10-13T11:46:56 Z Trickster Monkey and Apple-trees (IZhO12_apple) C++14
100 / 100
 331 ms 4088 KB 
#include <algorithm>
#include <string.h>
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
#include <map>

using namespace std;

#define lm (1<<30)
#define N 200010
#define ff first
#define ss second
#define ll long long
#define pb push_back
#define mod 1000000007
#define pii pair <ll, ll>
#define sz(a) int(a.size())
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
ll bigmod(ll a,ll e) {if(e==0)return 1;ll x=bigmod(a*a%mod,e>>1);return e&1?x*a%mod:x;}

int T[N], L[N], R[N];
int nodes, q, c, tp, l, r;

int lft(int node)
{
    if(L[node] == -1) L[node] = ++nodes;
    return L[node];
}
int rgh(int node)
{
    if(R[node] == -1) R[node] = ++nodes;
    return R[node];
}

void upd(int a, int b, int l, int r, int node)
{
    if(l > b || r < a || T[node] == r-l+1) return;

    if(l >= a && r <= b) {
        T[node] = r-l+1;
        return;
    }

    upd(a, b, l, (l+r)/2, lft(node));
    upd(a, b, (l+r)/2+1, r, rgh(node));

    T[node] = T[L[node]] + T[R[node]];
}
int tap(int a, int b, int l, int r, int node)
{
    if(l > b || r < a || node == -1) return 0;

    if(l >= a && r <= b) return T[node];

    if(T[node] == r-l+1) return min(r, b) - max(l, a) + 1;

    return tap(a, b, l, (l+r)/2, L[node]) + tap(a, b, (l+r)/2+1, r, R[node]);
}

int main()
{
    for(int i = 0; i <= 100000; i++) L[i] = R[i] = -1;

    cin >> q;

    while(q--) {
        cin >> tp >> l >> r;

        l += c, r += c;

        if(tp == 1) c = tap(l, r, 1, lm, 0), cout << c << "\n";
        else upd(l, r, 1, lm, 0);
    }
}

Compilation message

apple.cpp:23: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
   23 | #pragma GCC optimization ("O3")
      | 
apple.cpp:24: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
   24 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1152 KB Output is correct
2 Correct 1 ms 1152 KB Output is correct
3 Correct 1 ms 1152 KB Output is correct
4 Correct 24 ms 1280 KB Output is correct
5 Correct 30 ms 1400 KB Output is correct
6 Correct 30 ms 1280 KB Output is correct
7 Correct 30 ms 1400 KB Output is correct
8 Correct 147 ms 2132 KB Output is correct
9 Correct 289 ms 3192 KB Output is correct
10 Correct 293 ms 3324 KB Output is correct
11 Correct 294 ms 3324 KB Output is correct
12 Correct 298 ms 3476 KB Output is correct
13 Correct 318 ms 3704 KB Output is correct
14 Correct 325 ms 4088 KB Output is correct
15 Correct 316 ms 3704 KB Output is correct
16 Correct 328 ms 4088 KB Output is correct
17 Correct 321 ms 3704 KB Output is correct
18 Correct 331 ms 3836 KB Output is correct
19 Correct 319 ms 3832 KB Output is correct
20 Correct 323 ms 3960 KB Output is correct