Submission #932967

# Submission time Handle Problem Language Result Execution time Memory
932967 2024-02-24T16:25:29 Z AtabayRajabli Monkey and Apple-trees (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(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);
    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);
    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);
        }
    }
}
# Verdict Execution time Memory Grader output
1 Correct 56 ms 200808 KB Output is correct
2 Correct 56 ms 200788 KB Output is correct
3 Correct 49 ms 200664 KB Output is correct
4 Correct 57 ms 201004 KB Output is correct
5 Correct 59 ms 200920 KB Output is correct
6 Correct 60 ms 200864 KB Output is correct
7 Correct 61 ms 201036 KB Output is correct
8 Correct 157 ms 201796 KB Output is correct
9 Correct 292 ms 202612 KB Output is correct
10 Correct 300 ms 202068 KB Output is correct
11 Correct 312 ms 202428 KB Output is correct
12 Correct 302 ms 202268 KB Output is correct
13 Correct 251 ms 203116 KB Output is correct
14 Correct 260 ms 202404 KB Output is correct
15 Execution timed out 2636 ms 262144 KB Time limit exceeded
16 Halted 0 ms 0 KB -