oj.uz

Submission #932973

# Submission time Handle Problem Language Result Execution time Memory
932973 2024-02-24T16:34:20 Z AtabayRajabli Monkey and Apple-trees (IZhO12_apple) C++17
100 / 100
 404 ms 253840 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 * 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

# Verdict Execution time Memory 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