Submission #409654

#TimeUsernameProblemLanguageResultExecution timeMemory
409654tempusStrange Device (APIO19_strange_device)C++17
5 / 100
581 ms51620 KiB
#include <bits/stdc++.h> #define ll long long #define endl "\n" #define ios ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0); using namespace std; int main() { ios int n; cin >> n; ll A, B; cin >> A >> B; ll S = 0; map <ll, ll> was; ll l[n], r[n], ans = 0; for (int i = 0; i < n; ++ i) { cin >> l[i] >> r[i]; S += r[i] - l[i] + 1; }/* if (A > 1e18 / B + 1) { cout << S; return 0; }*/ ll val = A * B / __gcd(B - 1, A); vector <pair <ll, ll> > v; for (int i = 0; i < n; ++ i) { if (l[i] + val <= r[i]) { cout << val; return 0; } ll ml = l[i] % val, mr = r[i] % val; if (ml <= mr) { v.push_back({ml, mr}); } else { v.push_back({0, mr}); v.push_back({ml, val - 1}); } } sort(v.begin(), v.end()); ans = v[0].second - v[0].first + 1;/* for (int i = 0; i < v.size(); ++ i) { cout << v[i].first << " " << v[i].second << endl; }+*/ for (int i = 1; i < v.size(); ++ i) { ll nl = v[i].first, nr = v[i].second; if (nl > v[i - 1].second) { ans += nr - nl + 1; continue; } else if (nr <= v[i - 1].second) { v[i].second = v[i - 1].second; } else { ans += nr - v[i - 1].second; } } cout << ans; //3 3 3 4 4 7 9 17 18 return 0; }

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int i = 1; i < v.size(); ++ i) {
      |                     ~~^~~~~~~~~~
#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...