Submission #155037

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
155037	2019-09-25T22:21:52 Z	jovan_b	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	93 ms	17016 KB

apple

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

int c;
const int INF = 1000000000;

struct segment{
    int val;
    int l, r;
    int lazy;
} seg[10000000];

int cnt = 1;

void create(int node, int l, int r){
    seg[node].l = ++cnt;
    seg[node].r = ++cnt;
    int mid = ((ll)l+r)/2;
    if(seg[node].lazy){
        seg[cnt-1].val = mid-l+1;
        seg[cnt-1].lazy = 1;
        seg[cnt].val = r-mid;
        seg[cnt].lazy = 1;
    }
}

void propagate(int node, int l, int r){
    if(!seg[node].lazy) return;
    seg[node].val = r-l+1;
    if(l == r) return;
    if(!seg[node].l) create(node, l, r);
    int mid = (l+r)/2;
    seg[seg[node].l].val = mid-l+1;
    seg[seg[node].r].val = r-mid;
}

void upd(int node, int l, int r, int tl, int tr){
    propagate(node, l, r);
    if(tl > r || l > tr) return;
    if(tl <= l && r <= tr){
        seg[node].lazy = 1;
        seg[node].val = r-l+1;
        propagate(node, l, r);
        return;
    }
    int mid = ((ll)l+r)/2;
    if(!seg[node].l) create(node, l, r);
    upd(seg[node].l, l, mid, tl, tr);
    upd(seg[node].r, mid+1, r, tl, tr);
    seg[node].val = seg[seg[node].l].val + seg[seg[node].r].val;
}

int query(int node, int l, int r, int tl, int tr){
    propagate(node, l, r);
    if(tl > r || l > tr) return 0;
    if(tl <= l && r <= tr) return seg[node].val;
    if(seg[node].val == 0) return 0;
    if(seg[node].lazy == 1) return min(r, tr) - max(tl, l) + 1;
    int mid = ((ll)l+r)/2;
    return query(seg[node].l, l, mid, tl, tr) + query(seg[node].r, mid+1, r, tl, tr);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int m;
    cin >> m;
    while(m--){
        int a, l, r;
        cin >> a >> l >> r;
        l += c;
        r += c;
        if(a == 2){
            upd(1, 1, INF, l, r);
        }
        if(a == 1){
            c = query(1, 1, INF, l, r);
            cout << c << "\n";
        }
    }
    return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	14 ms	2296 KB	Output is correct
5	Correct	17 ms	2424 KB	Output is correct
6	Correct	18 ms	2424 KB	Output is correct
7	Correct	17 ms	2428 KB	Output is correct
8	Incorrect	93 ms	17016 KB	Output isn't correct
9	Halted	0 ms	0 KB	-