Submission #956070

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
956070	2024-04-01T01:33:07 Z	Rifal	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	1770 ms	262144 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)/2;
    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+1);
    seg[indxr].sum = (r-(mid+1)+1);
}
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+1);
    }
    else {
        ll mid = (l+r)/2;
        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;
        Update(indxl,l,mid,L,R); Update(indxr,mid+1,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)/2;
        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;
        return sol(indxl,l,mid,L,R)+sol(indxr,mid+1,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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	9 ms	6748 KB	Output is correct
5	Correct	11 ms	8880 KB	Output is correct
6	Correct	11 ms	8872 KB	Output is correct
7	Correct	11 ms	8796 KB	Output is correct
8	Correct	98 ms	52052 KB	Output is correct
9	Correct	200 ms	89380 KB	Output is correct
10	Correct	201 ms	99544 KB	Output is correct
11	Correct	189 ms	107600 KB	Output is correct
12	Correct	197 ms	111660 KB	Output is correct
13	Correct	176 ms	137040 KB	Output is correct
14	Correct	174 ms	138280 KB	Output is correct
15	Runtime error	1770 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-