Submission #393504

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
393504	2021-04-23T16:17:23 Z	SavicS	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	567 ms	165188 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[100 * maxn], rs[100 * maxn], root, lenj[100 * maxn];
ll bor[100 * 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

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	23 ms	3712 KB	Output is correct
5	Correct	28 ms	4556 KB	Output is correct
6	Correct	28 ms	4364 KB	Output is correct
7	Correct	28 ms	4544 KB	Output is correct
8	Correct	203 ms	32324 KB	Output is correct
9	Correct	421 ms	54980 KB	Output is correct
10	Correct	427 ms	61560 KB	Output is correct
11	Correct	463 ms	66812 KB	Output is correct
12	Correct	444 ms	69092 KB	Output is correct
13	Correct	399 ms	85940 KB	Output is correct
14	Correct	393 ms	86724 KB	Output is correct
15	Correct	567 ms	158860 KB	Output is correct
16	Correct	555 ms	161360 KB	Output is correct
17	Correct	406 ms	91872 KB	Output is correct
18	Correct	389 ms	91972 KB	Output is correct
19	Correct	551 ms	165164 KB	Output is correct
20	Correct	563 ms	165188 KB	Output is correct