제출 #1276099

#제출 시각아이디문제언어결과실행 시간메모리
1276099bbldrizzy이상한 기계 (APIO19_strange_device)C++20
5 / 100
1336 ms99328 KiB
#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); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...