답안 #932963

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
932963 2024-02-24T16:17:34 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(!lz[ind])return;
    if(li[ind] == -1)li[ind] = ++cnt;
    if(ri[ind] == -1)ri[ind] = ++cnt;
    //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)
{
    if(li[ind] == -1)li[ind] = ++cnt;
    if(ri[ind] == -1)ri[ind] = ++cnt;
    relax(ind, l, r);
    if(l > rx || r < lx)return 0;
    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);
    else relax(li[ind], l, mid);
    if(mid + 1 <= rx)res += get(ri[ind], mid + 1, r, lx, rx);
    else relax(ri[ind], mid + 1, r);
    return res;
}

void upd(int ind, int l, int r, int lx, int rx)
{
    if(li[ind] == -1)li[ind] = ++cnt;
    if(ri[ind] == -1)ri[ind] = ++cnt;
    //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);
    else relax(li[ind], l, mid);
    if(mid + 1 <= rx)upd(ri[ind], mid + 1, r, lx, rx);
    else 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 50 ms 200788 KB Output is correct
2 Correct 51 ms 200752 KB Output is correct
3 Correct 53 ms 200684 KB Output is correct
4 Correct 61 ms 200888 KB Output is correct
5 Correct 65 ms 200832 KB Output is correct
6 Correct 63 ms 200888 KB Output is correct
7 Correct 64 ms 200788 KB Output is correct
8 Correct 167 ms 200952 KB Output is correct
9 Correct 309 ms 201040 KB Output is correct
10 Correct 324 ms 201440 KB Output is correct
11 Correct 331 ms 201448 KB Output is correct
12 Correct 337 ms 201232 KB Output is correct
13 Correct 262 ms 201408 KB Output is correct
14 Correct 265 ms 201340 KB Output is correct
15 Execution timed out 2476 ms 262144 KB Time limit exceeded
16 Halted 0 ms 0 KB -