Submission #393505

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
393505	2021-04-23T16:18:47 Z	SavicS	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	616 ms	262144 KB

apple

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 100005;
const int inf = 1e9 + 5;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)

int n, q;

int idx = 0;
int ls[70 * maxn], rs[70 * maxn], root, lenj[70 * maxn];
ll bor[70 * maxn];

void propagate(int v, int tl, int tr) {
    if(lenj[v] != -1) {
        bor[v] = (tr - tl + 1) * 1ll * lenj[v];
        if(tl != tr) {
            if(ls[v] == 0)ls[v] = ++idx;
            lenj[ls[v]] = lenj[v];
            if(rs[v] == 0)rs[v] = ++idx;
            lenj[rs[v]] = lenj[v];
        }
        lenj[v] = -1;
    }
}

void lazyupd(int &v, int tl, int tr, int l, int r, int val) {
    if(!v) {
        v = ++idx;
        lenj[v] = -1;
    }
    propagate(v, tl, tr);
    if(tl > tr || tl > r || l > tr)return;
    if(tl >= l && tr <= r) {
        bor[v] = (tr - tl + 1) * 1ll * val;
        if(tl != tr) {
            if(ls[v] == 0)ls[v] = ++idx;
            lenj[ls[v]] = val;
            if(rs[v] == 0)rs[v] = ++idx;
            lenj[rs[v]] = val;
        }
        return;
    }
    int mid = (tl + tr) / 2;
    lazyupd(ls[v], tl, mid, l, r, val);
    lazyupd(rs[v], mid + 1, tr, l, r, val);
    bor[v] = bor[ls[v]] + bor[rs[v]];
}

ll kveri(int v, int tl, int tr, int l, int r) {
    propagate(v, tl, tr);
    if(!v || tl > r || l > tr)return 0;
    if(tl >= l && tr <= r)return bor[v];
    int mid = (tl + tr) / 2;
    return kveri(ls[v], tl, mid, l, r) + kveri(rs[v], mid + 1, tr, l, r);
}

int main() 
{
    ios::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);
    cin >> q;

    const int N = (int)1e9;

    int last = 0;
    while(q--) {
        int t, l, r;
        cin >> t >> l >> r;

        l += last, r += last;

        if(t == 2) {
            lazyupd(root, 1, N, l, r, 1);
        }

        if(t == 1) {
            last = kveri(root, 1, N, l, r);
            cout << last << endl;
        }

    }
    return 0;
}
/**



// probati bojenje sahovski ili slicno

**/

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	23 ms	3784 KB	Output is correct
5	Correct	28 ms	4540 KB	Output is correct
6	Correct	28 ms	4292 KB	Output is correct
7	Correct	28 ms	4436 KB	Output is correct
8	Correct	194 ms	32324 KB	Output is correct
9	Correct	408 ms	54844 KB	Output is correct
10	Correct	430 ms	61668 KB	Output is correct
11	Correct	426 ms	66884 KB	Output is correct
12	Correct	439 ms	69100 KB	Output is correct
13	Correct	386 ms	85852 KB	Output is correct
14	Correct	392 ms	86748 KB	Output is correct
15	Runtime error	616 ms	262144 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-