Submission #781633

#	Time	Username	Problem	Language	Result	Execution time	Memory
781633		makanhulia	Strange Device (APIO19_strange_device)	C++17	100 / 100	362 ms	33980 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;
#define int long long


signed main() {
  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  int n, a, b, c;
  cin >> n >> a >> b;
  vector<pair<int, int>> v;
  int arr[n], ARR[n];
  for(int i = 0; i < n; i++) {
    cin >> arr[i] >> ARR[i];
  }
  
  c = b + 1;
  int d = __gcd(c, a);
  int e;
  string s = to_string(a);
  string t = to_string(b);
  string q = to_string(d);
  if(s.length() + t.length() - q.length() > 18) {
    e = 1000000000000000000;
  } else {
    e = a / d;
    e *= b;
  }
  
  for(int i = 0; i < n; i++) {
    if(ARR[i] - arr[i] + 1 >= e) {
      cout << e << "\n";
      return 0;
    }
    if((ARR[i] % e) <= (arr[i] % e) && arr[i] < ARR[i]) {
      v.push_back({0, ARR[i] % e});
      v.push_back({arr[i] % e, e - 1});
    } else {
      v.push_back({arr[i] % e, ARR[i] % e});
    }
  }
  sort(v.begin(), v.end());
  int jum = 0, ka = -1;
  for(int i = 0; i < v.size(); i++) {
    if(v[i].first <= ka) {
      if(v[i].second <= ka) {
        
      } else {
        jum += v[i].second - ka;
        ka = v[i].second;
      }
    } else {
      jum += v[i].second - v[i].first + 1;
      ka = v[i].second;
    }
  }
  cout << jum << "\n";
  
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:43:20: 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]
   43 |   for(int i = 0; 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