oj.uz

Submission #781908

# Submission time Handle Problem Language Result Execution time Memory
781908 2023-07-13T13:06:46 Z makanhulia Strange Device (APIO19_strange_device) C++17
20 / 100
 464 ms 40656 KB 
#include<bits/stdc++.h>
#define int long long
#define pii pair<int, int>
using namespace std;
const int MAX=1e18;
signed main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int n, a, b; cin >> n >> a >> b;
  priority_queue<pii, vector<pii>, greater<pii>> pq;
  int S=0;
  bool cut=1;
    while(n--) {
      int l, r; cin >> l >> r;
      pq.push({l, r});
      S+=r-l+1;
      if(S>(int)1e6) cut=0, S=0;
    }
    if(cut) {
      set<pair<int, int>> ans;
      while(!pq.empty()) {
      int i=pq.top().first, j=pq.top().second;
      pq.pop();
        while(i<=j) {
        while(!pq.empty() && pq.top().first==i) j=max(j, pq.top().second);
          ans.insert({(i+i/b)%a, i%b});
            i++;
        }
      }
      cout << ans.size() << '\n';
  } else {
    priority_queue<pii, vector<pii>, greater<pii>> to_ans;
      int Mod;
      if(a>(MAX+b-1)/b) Mod=1e18+1;
      else Mod=a*b;
      while(!pq.empty()) {
        int l=pq.top().first, r=pq.top().second;
        pq.pop();
        while(!pq.empty() && pq.top().first<=r) r=max(r, pq.top().second), pq.pop();
      if((l+Mod-1)/Mod*Mod+Mod-1<=r) {cout << Mod << '\n'; return 0;}
        if((l+Mod-1)/Mod*Mod<=r && l%Mod) to_ans.push({l%Mod, Mod-1}), to_ans.push({0, r%Mod});
        else to_ans.push({l%Mod, r%Mod});
      }
      int ans=0;
      while(!to_ans.empty()) {
        int l=to_ans.top().first, r=to_ans.top().second;
        to_ans.pop();
        while(!to_ans.empty() && to_ans.top().first<=r) r=max(r, to_ans.top().second), to_ans.pop(); 
      ans+=r-l+1;
    }
    cout << ans << '\n';
  }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 40 ms 12396 KB Output is correct
3 Correct 62 ms 18012 KB Output is correct
4 Correct 2 ms 848 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 7 ms 1108 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 33 ms 7000 KB Output is correct
16 Correct 26 ms 6892 KB Output is correct
17 Correct 62 ms 8100 KB Output is correct
18 Correct 0 ms 212 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 104 ms 32284 KB Output is correct
3 Correct 138 ms 32072 KB Output is correct
4 Correct 108 ms 30580 KB Output is correct
5 Correct 427 ms 40656 KB Output is correct

Subtask #4
0 / 5.0

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 46 ms 4952 KB Output is correct
3 Correct 41 ms 4928 KB Output is correct
4 Correct 441 ms 40532 KB Output is correct
5 Correct 42 ms 4988 KB Output is correct
6 Correct 41 ms 4876 KB Output is correct
7 Correct 47 ms 5060 KB Output is correct
8 Correct 42 ms 4956 KB Output is correct
9 Correct 47 ms 4996 KB Output is correct
10 Correct 43 ms 4948 KB Output is correct
11 Correct 42 ms 4904 KB Output is correct
12 Correct 42 ms 4888 KB Output is correct
13 Correct 42 ms 4972 KB Output is correct
14 Correct 454 ms 40568 KB Output is correct
15 Incorrect 42 ms 4912 KB Output isn't correct
16 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 Correct 40 ms 12396 KB Output is correct
3 Correct 62 ms 18012 KB Output is correct
4 Correct 2 ms 848 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 7 ms 1108 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 33 ms 7000 KB Output is correct
16 Correct 26 ms 6892 KB Output is correct
17 Correct 62 ms 8100 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 104 ms 32284 KB Output is correct
26 Correct 138 ms 32072 KB Output is correct
27 Correct 108 ms 30580 KB Output is correct
28 Correct 427 ms 40656 KB Output is correct
29 Correct 0 ms 212 KB Output is correct
30 Correct 458 ms 40548 KB Output is correct
31 Incorrect 464 ms 40600 KB Output isn't correct
32 Halted 0 ms 0 KB -