Submission #1276099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276099		bbldrizzy	Strange Device (APIO19_strange_device)	C++20	5 / 100	1336 ms	99328 KiB

strange_device

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

class SparseSegtree {
  private:
	struct Node {
		ll freq = 0;
		ll lazy = 0;
		ll left = -1;
		ll right = -1;
	};
	vector<Node> tree;
	const ll n;
	ll timer = 0;

	ll comb(ll a, ll b) { return a + b; }

	void apply(ll cur, ll len, ll val) {
		if (val == 1) {
			tree[cur].lazy = val;
			tree[cur].freq = len * val;
		}
	}

	void push_down(ll cur, ll l, ll r) {
		if (tree[cur].left == -1) {
			tree[cur].left = ++timer;
			tree.push_back(Node());
		}
		if (tree[cur].right == -1) {
			tree[cur].right = ++timer;
			tree.push_back(Node());
		}
		ll m = (l + r) / 2;
		apply(tree[cur].left, m - l + 1, tree[cur].lazy);
		apply(tree[cur].right, r - m, tree[cur].lazy);
		tree[cur].lazy = 0;
	}

	void range_set(ll cur, ll l, ll r, ll ql, ll qr, ll val) {
		if (qr < l || ql > r) { return; }
		if (ql <= l && r <= qr) {
			apply(cur, r - l + 1, val);
		} else {
			push_down(cur, l, r);
			ll m = (l + r) / 2;
			range_set(tree[cur].left, l, m, ql, qr, val);
			range_set(tree[cur].right, m + 1, r, ql, qr, val);
			tree[cur].freq =
			    comb(tree[tree[cur].left].freq, tree[tree[cur].right].freq);
		}
	}

	ll range_sum(ll cur, ll l, ll r, ll ql, ll qr) {
		if (qr < l || ql > r) { return 0; }
		if (ql <= l && r <= qr) { return tree[cur].freq; }
		push_down(cur, l, r);
		ll m = (l + r) / 2;
		return comb(range_sum(tree[cur].left, l, m, ql, qr),
		            range_sum(tree[cur].right, m + 1, r, ql, qr));
	}

  public:
	SparseSegtree(ll n, ll q = 0) : n(n) {
		if (q > 0) { tree.reserve(2 * q * __lg(n)); }
		tree.push_back(Node());
	}

	void range_set(ll ql, ll qr, ll val) { range_set(0, 0, n - 1, ql, qr, val); }

	ll range_sum(ll ql, ll qr) { return range_sum(0, 0, n - 1, ql, qr); }
};

int main() {
    ll n, a, b; cin >> n >> a >> b;
    ll bruda = ((b%a) == a-1) ? a : -1;
    if (bruda == -1) {
        if (a > (ll)1e18/b) {
            bruda = (ll)1e18+1;
        } else {
            bruda = a*b;
        }
    }
    set<pair<ll, ll>> st;
    SparseSegtree seg(bruda, 2*n);
    for (int i = 0; i < n; i++) {
        ll a1, b1; cin >> a1 >> b1;
        if (b1 - a1 >= bruda) {
            cout << bruda; exit(0);
        } 
        a1 %= bruda;
        b1 %= bruda;
        if (a1 > b1) {
            seg.range_set(a1, bruda-1, 1);
            seg.range_set(0, b1, 1);
        } else {
            seg.range_set(a1, b1, 1);
        }
    }    
    cout << seg.range_sum(0, bruda);
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 5
• Subtask 3: 5 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 30