Submission #1223845

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223845		kunzaZa183	Strange Device (APIO19_strange_device)	C++20	100 / 100	4900 ms	376220 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n;
  ll A, B;
  cin >> n >> A >> B;
  vector<ll> l(n), r(n);
  for (int i = 0; i < n; i++)
    cin >> l[i] >> r[i];
  ll reps = A / __gcd(A, B + 1);

  map<ll, vector<pair<ll, bool>>> mlvl;
  mlvl[B] = {};
  map<ll, ll> mli;
  for (int i = 0; i < n; i++) {
    ll row1 = l[i] / B, row2 = r[i] / B;
    if (row1 == row2) {
      mlvl[l[i] % B].emplace_back(row1, 1);
      mlvl[r[i] % B + 1].emplace_back(row1, 0);
    } else {
      mlvl[l[i] % B].emplace_back(row1, 1);
      mlvl[B].emplace_back(row1, 0);
      if (row1 + 1 < row2) {
        ll lr = row1 + 1, rr = row2 - 1;
        if (rr - lr + 1 >= reps) {
          cout << reps * B << "\n";
          return 0;
        }
        lr %= reps, rr %= reps;
        if (lr <= rr) {
          mli[lr]++;
          mli[rr + 1]--;
        } else {
          mli[lr]++;
          mli[reps]--;
          mli[0]++;
          mli[rr + 1]--;
        }
      }
      mlvl[0].emplace_back(row2, 1);
      mlvl[r[i] % B + 1].emplace_back(row2, 0);
    }
  }

  vector<pair<ll, ll>> perm;
  ll ct = 0;
  for (auto a : mli) {
    if (ct == 0 && a.second >= 0) {
      perm.emplace_back(a.first, -1);
    } else if (ct > 0 && ct + a.second == 0) {
      perm.back().second = a.first;
    }
    ct += a.second;
  }

  map<ll, int> temp;

  ll sumrn = 0;
  for (auto a : perm)
    sumrn += a.second - a.first;

  ll cur = 0, ans = 0;
  for (auto &[in, vpllb] : mlvl) {
    ans += (in - cur) * sumrn;

    for (auto [row, stat] : vpllb) {
      row %= reps;
      auto it = upper_bound(perm.begin(), perm.end(),
                            make_pair(row, LLONG_MAX));
      if (it == perm.begin() || row >= (it - 1)->second) {
        if (stat) {
          temp[row]++;
          if (temp[row] == 1)
            sumrn++;
        } else {
          temp[row]--;
          if (temp[row] == 0)
            sumrn--;
        }
      }
    }
    cur = in;
  }

  cout << ans << "\n";
}

• 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