제출 #848257

#제출 시각아이디문제언어결과실행 시간메모리
848257popovicirobert이상한 기계 (APIO19_strange_device)C++14
100 / 100
1296 ms100452 KiB
#include <bits/stdc++.h> #define lsb(x) (x & (-x)) using ull = unsigned long long; using ll = long long; using namespace std; constexpr ll INF = 3e18; int main() { #ifdef HOME ifstream cin("input.in"); ofstream cout("output.out"); #endif ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int n; ll a, b; cin >> n >> a >> b; ll period; if (INF / b < a / __gcd(a, b + 1)) { period = INF; } else { period = (a / __gcd(a, b + 1)) * b; } multiset<pair<ll, ll>> mst; for (int i = 0; i < n; i++) { ll l, r; cin >> l >> r; if (r - l + 1 >= period) { cout << period << "\n"; return 0; } auto Add = [&](ll l, ll r) { ll new_l = l, new_r = r; vector<pair<ll, ll>> temp; auto itr = mst.insert({l, r}); auto prv = itr; while (prv != mst.begin() && prv->second >= l) { new_l = min(new_l, prv->first); new_r = max(new_r, prv->second); temp.push_back(*prv); prv = prev(prv); } if (prv->second >= l) { new_l = min(new_l, prv->first); new_r = max(new_r, prv->second); temp.push_back(*prv); temp.push_back(*prv); } auto nxt = itr; while (nxt != mst.end() && nxt->first <= r) { new_l = min(new_l, nxt->first); new_r = max(new_r, nxt->second); temp.push_back(*nxt); nxt = next(nxt); } for (auto s : temp) { mst.erase(s); } mst.insert({new_l, new_r}); }; l %= period; r %= period; if (l > r) { Add(l, period - 1); Add(0, r); } else { Add(l, r); } } ll answer = 0; for (auto itr : mst) { answer += itr.second - itr.first + 1; } cout << answer; return 0; }
#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...