Submission #781905

#	Time	Username	Problem	Language	Result	Execution time	Memory
781905		makanhulia	Strange Device (APIO19_strange_device)	C++17	100 / 100	376 ms	18580 KiB

strange_device

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define keish                             ios_base::sync_with_stdio(0);       cin.tie(0); cout.tie(0)
      
using namespace std;

int n, a, b, l, r;

signed main(){
      keish;
      cin >> n >> a >> b;

      int c = a / gcd(a, b + 1);
      if(c > 1e18 / b) c = 1e18;
      else c *= b;
      
      vector<pair<int, int>> v;
      bool ok = 0;
      for(int i = 0; i < n; i++){
            cin >> l >> r;
            if(r - l + 1 >= c){
                  ok = 1;
            }

            l %= c, r %= c;

            if(l <= r){
                  v.push_back({l, r});
            }else{
                  v.push_back({l, c - 1});
                  v.push_back({0, r});
            }
      }

      if(ok){
            cout << c << '\n';
            return 0;
      }

      sort(v.begin(), v.end());

      int lf = v[0].fi, rg = v[0].se;
      int ans = 0;
      for(int i = 1; i < v.size(); i++){
            if(v[i].fi > rg){
                  ans += rg - lf + 1;
                  lf = v[i].fi, rg = v[i].se;
            }
            rg = max(rg, v[i].se);
      }
      ans += rg - lf + 1;

      cout << ans << '\n';
}     

Compilation message (stderr)

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

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