Submission #932962

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
932962	2024-02-24T16:17:11 Z	AtabayRajabli	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	315 ms	205872 KB

apple

#include <bits/stdc++.h>

// author : a1abay

#define all(v)      v.begin(), v.end()
#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);
        }
    }
}

Compilation message

apple.cpp:12:34: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   12 | const int inff =            1e18 + 7;
      |                             ~~~~~^~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	100440 KB	Output is correct
2	Correct	23 ms	100436 KB	Output is correct
3	Correct	22 ms	100444 KB	Output is correct
4	Correct	32 ms	100680 KB	Output is correct
5	Correct	32 ms	100692 KB	Output is correct
6	Correct	33 ms	100444 KB	Output is correct
7	Correct	33 ms	100720 KB	Output is correct
8	Correct	132 ms	100828 KB	Output is correct
9	Correct	253 ms	100944 KB	Output is correct
10	Correct	277 ms	101092 KB	Output is correct
11	Correct	259 ms	100972 KB	Output is correct
12	Correct	251 ms	101464 KB	Output is correct
13	Correct	210 ms	101092 KB	Output is correct
14	Correct	220 ms	101004 KB	Output is correct
15	Runtime error	315 ms	205872 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-