답안 #932973

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
932973	2024-02-24T16:34:20 Z	AtabayRajabli	원숭이와 사과 나무 (IZhO12_apple)	C++17	100 / 100	404 ms	253840 KB

apple

#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 * 80, -1), ri(sz * 80, -1);
vector<int> sg(sz * 80, 0), lz(sz * 80, 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]] = 1;
    lz[ri[ind]] = 1;
    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);
        }
    }
}

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	72 ms	250708 KB	Output is correct
2	Correct	71 ms	250960 KB	Output is correct
3	Correct	69 ms	250708 KB	Output is correct
4	Correct	76 ms	250956 KB	Output is correct
5	Correct	79 ms	250860 KB	Output is correct
6	Correct	77 ms	250884 KB	Output is correct
7	Correct	76 ms	250960 KB	Output is correct
8	Correct	180 ms	251000 KB	Output is correct
9	Correct	301 ms	251220 KB	Output is correct
10	Correct	318 ms	251528 KB	Output is correct
11	Correct	334 ms	251476 KB	Output is correct
12	Correct	317 ms	251232 KB	Output is correct
13	Correct	264 ms	251220 KB	Output is correct
14	Correct	265 ms	251340 KB	Output is correct
15	Correct	394 ms	252908 KB	Output is correct
16	Correct	395 ms	253524 KB	Output is correct
17	Correct	271 ms	253772 KB	Output is correct
18	Correct	269 ms	253460 KB	Output is correct
19	Correct	404 ms	253840 KB	Output is correct
20	Correct	392 ms	253520 KB	Output is correct