Submission #530821

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
530821	2022-02-26T21:47:34 Z	Evang	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	627 ms	256712 KB

apple

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

#ifdef _DEBUG
#define dout(x) clog << "Line " << __LINE__ << ": " << #x << "=" << (x) << el
#else
#define dout(x)
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define uid(a,b) uniform_int_distribution<int>(a,b)(rng)

#define ins insert
#define ssize(x) (int((x).size()))
#define bs(args...) binary_search(args)
#define lb(args...) lower_bound(args)
#define ub(args...) upper_bound(args)
#define all(x) (x).begin(),(x).end()
#define mp(a, b) make_pair(a, b)
#define mt(args...) make_tuple(args)
#define pb(x) push_back(x)
#define eb(args...) emplace_back(args)
#define ff first
#define ss second
#define die exit(0)

template<typename T>
using vc = vector<T>;
template<typename T>
using uset = unordered_set<T>;
template<typename A, typename B>
using umap = unordered_map<A, B>;
template<typename T, typename Comp>
using pq = std::priority_queue<T, vc<T>, Comp>;
template<typename T>
using maxpq = pq<T, less<T>>;
template<typename T>
using minpq = pq<T, greater<T>>;
template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

using db = double;
using ld = long double;
using ll = long long;
using ull = unsigned long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vc<int>;
using vll = vc<ll>;
using vpi = vc<pi>;
using vpll = vc<pll>;
using str = string;

constexpr char el = '\n';
constexpr char sp = ' ';
constexpr int inf = 0x3f3f3f3f;
constexpr ll llinf = 0x3f3f3f3f3f3f3f3fLL;
// ---------------------------------------------------------------------


const int N = 1<<30;
int q;
struct node {
    node *left = nullptr, *right = nullptr;
    int sum;
    bool set;
    node *l(){
        if(left==nullptr)
            left = new node;
        return left;
    }
    node *r(){
        if(right==nullptr)
            right = new node;
        return right;
    }
};

void push(node *v, int il, int ir){
    if(!v->set)
        return;
    if(il!=ir)
        v->l()->set = v->r()->set = 1;
    v->sum = ir-il+1;
    v->set = 0;
}

void pull(node *v){
    v->sum = v->r()->sum + v->l()->sum;
}

void upd(int l, int r, node *v, int il, int ir){
    push(v, il, ir);
    if(ir < l || r < il)
        return;
    if(l <= il && ir <= r){
        v->set = 1;
        push(v, il, ir);
        return;
    }

    int im = (il+ir)/2;
    upd(l, r, v->l(), il, im);
    upd(l, r, v->r(), im+1, ir);
    pull(v);
}

int qry(int l, int r, node *v, int il, int ir){
    push(v, il, ir);
    if(ir < l || r < il)
        return 0;
    if(l <= il && ir <= r)
        return v->sum;

    int im = (il+ir)/2;
    return qry(l, r, v->l(), il, im) + qry(l, r, v->r(), im+1, ir);
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cout << fixed; clog << fixed; clog << unitbuf;
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("debug.txt", "w", stderr);
#else
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
#endif

    cin >> q;
    node *root = new node;
    int c = 0;
    while(q--){
        int t, l, r;
        cin >> t >> l >> r;
        l += c;
        r += c;
        if(t==1)
            cout << (c = qry(l, r, root, 1, N)) << el;
        else
            upd(l, r, root, 1, N);
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	17 ms	5696 KB	Output is correct
5	Correct	20 ms	6912 KB	Output is correct
6	Correct	17 ms	6696 KB	Output is correct
7	Correct	18 ms	6864 KB	Output is correct
8	Correct	165 ms	50320 KB	Output is correct
9	Correct	347 ms	89232 KB	Output is correct
10	Correct	373 ms	96168 KB	Output is correct
11	Correct	367 ms	104388 KB	Output is correct
12	Correct	387 ms	107780 KB	Output is correct
13	Correct	327 ms	136064 KB	Output is correct
14	Correct	321 ms	137500 KB	Output is correct
15	Correct	595 ms	248676 KB	Output is correct
16	Correct	545 ms	250692 KB	Output is correct
17	Correct	316 ms	142396 KB	Output is correct
18	Correct	343 ms	142400 KB	Output is correct
19	Correct	627 ms	256544 KB	Output is correct
20	Correct	521 ms	256712 KB	Output is correct