Submission #206167

#	Time	Username	Problem	Language	Result	Execution time	Memory
206167		AlexLuchianov	Strange Device (APIO19_strange_device)	C++14	100 / 100	829 ms	47292 KiB

strange_device

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

using ll = long long;
using ld = long double;

ll const inf = 1000000000000000000;

ll period(ll a, ll b){
  ll p = __gcd(a, b + 1);
  if(a / p <= inf / b)
    return a / p * b;
  return inf + 1;
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  int n;
  ll a, b;
  cin >> n >> a >> b;
  ll pi = period(a, b);
  if(inf < pi){
    ll result = 0;
    for(int i = 1;i <= n; i++){
      ll x, y;
      cin >> x >> y;
      result += y - x + 1;
    }
    cout << result;
  } else {
    vector<pair<ll,int>> event;
    for(int i = 1;i <= n; i++){
      ll x, y;
      cin >> x >> y;
      if(y - x < pi){
        if(x % pi <= y % pi){
          event.push_back({x % pi, 1});
          event.push_back({y % pi + 1, -1});
        } else {
          event.push_back({x % pi, 1});
          event.push_back({pi, -1});
          event.push_back({0, 1});
          event.push_back({y % pi + 1, -1});
        }
      } else {
        cout << pi;
        return 0;
      }
    }
    sort(event.begin(), event.end());
    ll result = 0, last = 0, sum = 0;
    for(int i = 0; i < event.size(); i++){
      if(0 < sum)
        result += event[i].first - last;
      last = event[i].first;
      sum += event[i].second;
    }
    cout << result;
  }
  return 0;
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:62:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < event.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