Submission #729694

#TimeUsernameProblemLanguageResultExecution timeMemory
729694danikoynovStrange Device (APIO19_strange_device)C++14
5 / 100
5068 ms48948 KiB
#include<bits/stdc++.h> #define endl '\n' using namespace std; typedef long long ll; void speed() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } const int maxn = 1e6 + 10; int n; ll l[maxn], r[maxn]; ll A, B; struct point { ll x, t; point(ll _x = 0, ll _t = 0) { x = _x; t = _t; } bool operator < (const point &p) const { if (x == p.x) return t < p.t; return x < p.x; } }; vector < point > vec; void add_segment(int l, int r) { vec.push_back(point(l, 1)); vec.push_back(point(r, -1)); } void solve() { cin >> n >> A >> B; for (int i = 1; i <= n; i ++) { cin >> l[i] >> r[i]; } ll g = __gcd(A, B + 1); /// period is A * B / g if ((double)(1e18) / (double)(A) < (double)(B) / (double)(g)) { while(true); ll ans = 0; for (int i = 1; i <= n; i ++) { ans = ans + (r[i] - l[i] + 1); } cout << ans << endl; return; } long long period = (A / g) * B; for (int i = 1; i <= n; i ++) { if (r[i] - l[i] + 1 >= period) { cout << period << endl; return; } r[i] ++; ll x = l[i] % period, y = r[i] % period; if (x <= y) { add_segment(x, y); } else { add_segment(0, y); add_segment(x, period); } } sort(vec.begin(), vec.end()); ll ans = 0, cnt = 0; for (int i = 0; i < vec.size();) { int r = i; while(r < vec.size() && vec[i].x == vec[r].x) r ++; for (int j = i; j < r; j ++) cnt += vec[j].t; //cout << i << " : " << r << " " << cnt << " " << vec[r].x << " " << vec[i].x << endl; if (cnt > 0) ans = ans + vec[r].x - vec[i].x; i = r; } cout << ans << endl; } int main() { solve(); return 0; } /** 1 10000 3312452154131231 1 1 */

Compilation message (stderr)

strange_device.cpp: In function 'void solve()':
strange_device.cpp:94:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for (int i = 0; i < vec.size();)
      |                     ~~^~~~~~~~~~~~
strange_device.cpp:97:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |         while(r < vec.size() && vec[i].x == vec[r].x)
      |               ~~^~~~~~~~~~~~
#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...