oj.uz

답안 #312462

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
312462 2020-10-13T11:46:56 Z Trickster 원숭이와 사과 나무 (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

# 결과 실행 시간 메모리 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