oj.uz

Submission #519136

# Submission time Handle Problem Language Result Execution time Memory
519136 2022-01-25T18:02:44 Z cadmiumsky Strange Device (APIO19_strange_device) C++14
35 / 100
 1751 ms 100200 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main() {
  int a,b,q;
  bool ok = 0;
  cin >> q >> a >> b;
  map<int,int> smen;
  int per = a * b / __gcd(b + 1, a); // formula magica care e motivata din.. niste calcule de clasa a 7a de algebra modulara O_o
  if(log2((double)a / (double)__gcd(b + 1, a)) + log2(b) > 60)
    per = 1e18 + 1;
  for(int i = 0, cl, cr, l, r; i < q; i ++) {
    cin >> l >> r;
    cl = per * ceil((double)l / (double)per);
    cr = per * floor((double)r / (double)per);
    if(cl < cr) {
      ok = 1;
    }
    if(cl == cr && l < cl && cr <= r) {
      l %= per;
      r %= per;
      smen[l]++;
      smen[0]++;
      smen[r + 1]--;
      //cout << l <<  ' '<< -per - 1 << '\n' << 0 << ' ' << r << '\n';
    }
    else {
      l %= per;
      r %= per;
      smen[l]++;
      smen[r + 1]--;
      //cout << l << ' ' << r << '\n';
    }
  }
  if(ok) {
    cout << per << '\n';
    return 0;
  }
  smen[per];
  int total = 0, cnt = 0, last = -1;
  for(auto x : smen) {
    if(last != x.first && cnt > 0)
      total += x.first - last;
    if(x.first >= per)
      break;
    //cout << x.first <<  ' '<< x.second << '\n';
    cnt += x.second;
    last = x.first;
  }
  cout << total << '\n';
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 14 ms 1180 KB Output is correct
3 Correct 15 ms 1252 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 296 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Incorrect 1 ms 312 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 288 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Incorrect 2 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 1508 ms 100200 KB Output is correct
3 Correct 1600 ms 100112 KB Output is correct
4 Correct 1726 ms 100016 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 1508 ms 100200 KB Output is correct
3 Correct 1600 ms 100112 KB Output is correct
4 Correct 1726 ms 100016 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1652 ms 100124 KB Output is correct
7 Correct 1751 ms 100104 KB Output is correct
8 Correct 1697 ms 100108 KB Output is correct
9 Correct 1730 ms 100176 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 1508 ms 100200 KB Output is correct
3 Correct 1600 ms 100112 KB Output is correct
4 Correct 1726 ms 100016 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Correct 145 ms 10256 KB Output is correct
7 Correct 142 ms 10264 KB Output is correct
8 Correct 148 ms 10252 KB Output is correct
9 Correct 152 ms 10252 KB Output is correct
10 Correct 143 ms 10264 KB Output is correct
11 Correct 143 ms 10240 KB Output is correct
12 Correct 144 ms 10248 KB Output is correct
13 Correct 155 ms 10316 KB Output is correct
14 Correct 143 ms 10180 KB Output is correct
15 Correct 153 ms 10276 KB Output is correct
16 Correct 159 ms 10320 KB Output is correct
17 Correct 153 ms 10280 KB Output is correct
18 Correct 1518 ms 100044 KB Output is correct
19 Correct 1636 ms 100128 KB Output is correct
20 Correct 1661 ms 100108 KB Output is correct
21 Correct 148 ms 10156 KB Output is correct
22 Correct 145 ms 10176 KB Output is correct
23 Incorrect 418 ms 12812 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 155 ms 10212 KB Output is correct
3 Correct 154 ms 10216 KB Output is correct
4 Correct 1599 ms 100168 KB Output is correct
5 Correct 154 ms 10244 KB Output is correct
6 Correct 154 ms 10188 KB Output is correct
7 Correct 160 ms 10324 KB Output is correct
8 Correct 156 ms 10200 KB Output is correct
9 Correct 152 ms 10308 KB Output is correct
10 Correct 145 ms 10272 KB Output is correct
11 Correct 152 ms 10308 KB Output is correct
12 Correct 151 ms 10216 KB Output is correct
13 Correct 155 ms 10208 KB Output is correct
14 Correct 1672 ms 100092 KB Output is correct
15 Correct 143 ms 10268 KB Output is correct
16 Correct 1525 ms 100032 KB Output is correct
17 Correct 1525 ms 100132 KB Output is correct
18 Correct 0 ms 204 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 14 ms 1180 KB Output is correct
3 Correct 15 ms 1252 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 296 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Incorrect 1 ms 312 KB Output isn't correct
9 Halted 0 ms 0 KB -