Submission #788207

#	Time	Username	Problem	Language	Result	Execution time	Memory
788207		tvladm2009	Strange Device (APIO19_strange_device)	C++17	100 / 100	620 ms	100176 KiB

strange_device

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll INF = (ll) 1e18;

ll n, a, b;

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

  // freopen("input", stdin, "r");

  cin >> n >> a >> b;
  ll period = a / __gcd(b + 1, a);
  if (INF / period < b) {
    period = INF;
  } else {
    period *= b;
  }

  map<ll, int> jmen;

  function<void(ll, ll)> add = [&](ll l, ll r) {
    if (r - l + 1 >= period) {
      jmen[0]++;
    } else {
      l %= period;
      r %= period;
      if (l <= r) {
        jmen[l]++;
        jmen[r + 1]--;
      } else {
        jmen[l]++;
        jmen[period]--;

        jmen[0]++;
        jmen[r + 1]--;
      }
    }
  };

  for (int i = 1; i <= n; i++) {
    ll l, r;
    cin >> l >> r;
    add(l, r);
  }

  jmen[period] = 0;

  ll sol = 0;
  int s = 0;
  ll last = 0;
  for (auto &i : jmen) {
    if (s > 0) {
      sol += i.first - last;
    }
    s += i.second;
    last = i.first;
  }

  cout << sol << "\n";

  return 0;
}

• 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