Submission #191343

#	Time	Username	Problem	Language	Result	Execution time	Memory
191343		AlexPop28	Strange Device (APIO19_strange_device)	C++11	100 / 100	710 ms	69020 KiB

strange_device

#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<

// 0(B+1)    1    2    3    ...  B-2   B-1
// 1(B+1)  B+2  B+3  B+4  ...  2B-1  2B
// 2(B+1)  2B+3 ....
// ---
// X(B+1)
// vreau ca X(B+1) = 0 (mod A) => X(B+1) multiplu de A => X(B + 1) = lcm(A, B + 1)
// X(B + 1) = A * (B + 1) / GCD(A, B + 1) => X = A / GCD(A, B + 1)

using namespace std;

const long long INF = numeric_limits<long long>::max();

long long GCD(long long a, long long b) {
  if (!b) return a;
  return GCD(b, a % b);
}

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

  auto Print = [&](long long ans) {
    cout << ans << endl;
    exit(0);
  };

  long long n, a, b; cin >> n >> a >> b;
//  for (int t = 0; t < 20; ++t) {
//    dbg() (t + t / b) % a  << ' ' << t % b << endl;
//  }
  vector<pair<long long, long long>> segm(n);
  long long total = 0;
  for (auto &p : segm) {
    cin >> p.first >> p.second;
    total += p.second - p.first + 1;
  }

  long long x = a / GCD(a, b + 1);
  if (x >= INF / b) { // x e ft mare => in prima perioada
    Print(total);
  }

  long long t = x * b; // perioada
//  dbg() "perioada este " << name(t) endl;
  vector<pair<long long, long long>> v; v.reserve(2 * n);
  for (auto &p : segm) {
    if (p.second - p.first + 1 >= t) {
      Print(t);
    }
    p.first %= t; p.second %= t;
    if (p.first <= p.second) {
      v.emplace_back(p);
    } else {
      v.emplace_back(p.first, t - 1);
      v.emplace_back(0LL, p.second);
    }
  }
  sort(v.begin(), v.end());
  long long rgt = -1, ans = 0LL;
  for (auto &p : v) {
//    dbg() name(p.first) name(p.second) endl;
    if (p.second > rgt) {
      ans += p.second - max(p.first, rgt + 1) + 1;
      rgt = p.second;
    }
  }
  Print(ans); 
}

• 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