답안 #932969

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
932969 2024-02-24T16:28:12 Z AtabayRajabli 원숭이와 사과 나무 (IZhO12_apple) C++17
0 / 100
2000 ms 262144 KB
#include <bits/stdc++.h>

// author : a1abay

#define all(v)      v.begin(), v.end()
#define int         ll
#define gcd(a, b)   __gcd(a, b)
#define lcm(a, b)   (a*b / (__gcd(a, b)))
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

typedef long long           ll;
const int inf =             1e9 + 7;
const int inff =            1e18 + 7;
const int sz =              1e5 + 5;
using namespace             std;

int n, cnt = 1;
vector<int> li(sz * 64, -1), ri(sz * 64, -1);
vector<int> sg(sz * 64, 0), lz(sz * 64, 0);

void relax(int ind, int l, int r)
{
    if(li[ind] == -1)li[ind] = ++cnt;
    if(ri[ind] == -1)ri[ind] = ++cnt;
    if(!lz[ind])return;
    //cout << "relx : " << l << " " << r << endl;
    if(l == r)
    {
        sg[ind] = 1;
        lz[ind] = 0;
        return;
    }
    sg[ind] = r - l + 1;
    lz[li[ind]] = lz[ind];
    lz[ri[ind]] = lz[ind];
    lz[ind] = 0;
}

int get(int ind, int l, int r, int lx, int rx)
{
    relax(ind, l, r);
    if(lx <= l && r <= rx)return sg[ind];
    int mid = (l + r) >> 1, res = 0;
    if(lx <= mid)res += get(li[ind], l, mid, lx, rx);
    if(mid + 1 <= rx)res += get(ri[ind], mid + 1, r, lx, rx);
    return res;
}

void upd(int ind, int l, int r, int lx, int rx)
{
    //cout << "IN : " << l << " " << r << " " << sg[ind] << endl;
    relax(ind, l, r);

    if(lx <= l && r <= rx)
    {
        lz[ind] = 1;
        relax(ind, l, r);
        return;
    }
    int mid = (l + r) >> 1;

    if(lx <= mid)upd(li[ind], l, mid, lx, rx);
    relax(li[ind], l, mid);
    if(mid + 1 <= rx)upd(ri[ind], mid + 1, r, lx, rx);
    relax(ri[ind], mid + 1, r);
    sg[ind] = sg[li[ind]] + sg[ri[ind]];
    //cout << "OUT : " << endl;;
    //cout << l << " " << mid << " " << sg[li[ind]] << endl;
    //cout << mid + 1 << " " << r << " " << sg[ri[ind]] << endl;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    int c = 0;
    while(n--)
    {
        int d, x, y;
        cin >> d >> x >> y;
        if(d == 1)
        {
            c = get(1, 1, 1e9, x + c, y + c);
            cout << c << '\n';
        }
        else
        {
            upd(1, 1, 1e9, x + c, y + c);
        }
    }
}
# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 200788 KB Output is correct
2 Correct 49 ms 200740 KB Output is correct
3 Correct 52 ms 200780 KB Output is correct
4 Correct 57 ms 200784 KB Output is correct
5 Correct 60 ms 200788 KB Output is correct
6 Correct 61 ms 200728 KB Output is correct
7 Correct 60 ms 200788 KB Output is correct
8 Correct 166 ms 200964 KB Output is correct
9 Correct 300 ms 201272 KB Output is correct
10 Correct 307 ms 201164 KB Output is correct
11 Correct 302 ms 201420 KB Output is correct
12 Correct 311 ms 201296 KB Output is correct
13 Correct 253 ms 201452 KB Output is correct
14 Correct 246 ms 201276 KB Output is correct
15 Execution timed out 2542 ms 262144 KB Time limit exceeded
16 Halted 0 ms 0 KB -