Submission #956071

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
956071	2024-04-01T01:37:31 Z	Rifal	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	2000 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)/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;
        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;
        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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 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	6832 KB	Output is correct
5	Correct	11 ms	8796 KB	Output is correct
6	Correct	11 ms	8872 KB	Output is correct
7	Correct	11 ms	8796 KB	Output is correct
8	Correct	100 ms	51956 KB	Output is correct
9	Correct	205 ms	89172 KB	Output is correct
10	Correct	190 ms	99476 KB	Output is correct
11	Correct	218 ms	107604 KB	Output is correct
12	Correct	201 ms	111816 KB	Output is correct
13	Correct	192 ms	137044 KB	Output is correct
14	Correct	166 ms	138320 KB	Output is correct
15	Execution timed out	2465 ms	262144 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-