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

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 * 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);
        }
    }
}

Subtask #1

0 / 100.0

#	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	-