Submission #932961

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
932961	2024-02-24T16:16:51 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	54 ms	200788 KB	Output is correct
2	Correct	53 ms	200636 KB	Output is correct
3	Correct	52 ms	201060 KB	Output is correct
4	Correct	59 ms	200788 KB	Output is correct
5	Correct	61 ms	200784 KB	Output is correct
6	Correct	61 ms	200832 KB	Output is correct
7	Correct	61 ms	200788 KB	Output is correct
8	Correct	164 ms	201308 KB	Output is correct
9	Correct	321 ms	201124 KB	Output is correct
10	Correct	316 ms	201364 KB	Output is correct
11	Correct	347 ms	201040 KB	Output is correct
12	Correct	328 ms	201044 KB	Output is correct
13	Correct	260 ms	201296 KB	Output is correct
14	Correct	263 ms	201336 KB	Output is correct
15	Execution timed out	2470 ms	262144 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-