Submission #932963

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
932963	2024-02-24T16:17:34 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(!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);
        }
    }
}

Subtask #1

0 / 100.0

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