oj.uz

Submission #788206

# Submission time Handle Problem Language Result Execution time Memory
788206 2023-07-20T00:29:31 Z tvladm2009 Strange Device (APIO19_strange_device) C++17
0 / 100
 24 ms 364 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll INF = (ll) 1e18;

int 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 = [&](int l, int 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++) {
    int 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 316 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 24 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 24 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 24 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 3 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -