Submission #956075

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
956075	2024-04-01T02:00:59 Z	Rifal	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	251 ms	201948 KB

apple

#include <bits/stdc++.h>
#include <fstream>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define mod 1000000007
#define INF 1000000001
#define INF2 2000000000
///#define cin fin
///#define cout fout
using namespace std;
double const EPS = 1e-14;
const int P = 1007;
typedef long long ll;
///ofstream fout("herding.out");
///ifstream fin("herding.in");
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; // find_by_order, order_of_key
const int N = 1e5 + 5;
struct Node {
    ll sum = 0, numl = 0, numr = 0;
    bool lazy = false;
};
Node seg[N*64];
int cnt = 2;
void push(int x, ll l, ll r) {
    if(l == r || seg[x].lazy == false) return;
    ll mid = (l+r)/2ll;
    if(seg[x].numl == 0) {
        seg[x].numl = cnt; cnt++; }
    if(seg[x].numr == 0) {
        seg[x].numr = cnt; cnt++; }
    seg[x].lazy = false;
    int indxl = seg[x].numl, indxr = seg[x].numr;
    seg[indxl].lazy = true;
    seg[indxr].lazy = true;
    seg[indxl].sum = (mid-l+1ll);
    seg[indxr].sum = (r-(mid+1ll)+1ll);
}
void Update(int x, ll l, ll r, ll L, ll R) {
    push(x,l,r);
    if(l > R || r < L) {
        return;
    }
    else if(l >= L && r <= R) {
        seg[x].lazy = true;
        seg[x].sum = (r-l+1ll);
    }
    else {
        ll mid = (l+r)/2ll;
        if(seg[x].numl == 0) {
                seg[x].numl = cnt; cnt++;
        }
        if(seg[x].numr == 0) {
            seg[x].numr = cnt; cnt++;
        }
        int indxl = seg[x].numl, indxr = seg[x].numr;
        if(L > mid) {
            Update(indxr,mid+1ll,r,L,R);
        }
        else if(R <= mid) {
            Update(indxl,l,mid,L,R);
        }
        else {
            Update(indxl,l,mid,L,R); Update(indxr,mid+1ll,r,L,R);
        }
        seg[x].sum = seg[indxl].sum+seg[indxr].sum;
    }
}
ll sol(int x, ll l, ll r, ll L, ll R) {
    push(x,l,r);
    if(l > R || r < L) {
        return 0;
    }
    else if(l >= L && r <= R) {
        return seg[x].sum;
    }
    else {
        ll mid = (l+r)/2ll;
        if(seg[x].numl == 0) {
            seg[x].numl = cnt; cnt++;
        }
        if(seg[x].numr == 0) {
            seg[x].numr = cnt; cnt++;
        }
        int indxl = seg[x].numl, indxr = seg[x].numr;
        if(L > mid) {
            return sol(indxr,mid+1ll,r,L,R);
        }
        else if(R <= mid) {
            return sol(indxl,l,mid,L,R);
        }
        else {
        return sol(indxl,l,mid,L,R)+sol(indxr,mid+1ll,r,L,R);
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
    int m; cin >> m; ll c = 0;
    while(m--) {
        ll d, l, r; cin >> d >> l >> r;
        if(d == 1) {
            ll val = sol(1,1,INF,l+c,r+c);
            cout << val << endl; c = val;
        }
        else {
            Update(1,1,INF,l+c,r+c);
        }
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	12 ms	6748 KB	Output is correct
5	Correct	9 ms	6748 KB	Output is correct
6	Correct	11 ms	6748 KB	Output is correct
7	Correct	10 ms	6748 KB	Output is correct
8	Correct	93 ms	41800 KB	Output is correct
9	Correct	178 ms	70736 KB	Output is correct
10	Correct	188 ms	78916 KB	Output is correct
11	Correct	189 ms	85076 KB	Output is correct
12	Correct	180 ms	89012 KB	Output is correct
13	Correct	155 ms	105556 KB	Output is correct
14	Correct	153 ms	107604 KB	Output is correct
15	Correct	245 ms	195920 KB	Output is correct
16	Correct	239 ms	197716 KB	Output is correct
17	Correct	151 ms	113972 KB	Output is correct
18	Correct	149 ms	113780 KB	Output is correct
19	Correct	244 ms	201808 KB	Output is correct
20	Correct	251 ms	201948 KB	Output is correct