oj.uz

Submission #781632

# Submission time Handle Problem Language Result Execution time Memory
781632 2023-07-13T08:57:25 Z kebine Strange Device (APIO19_strange_device) C++17
10 / 100
 433 ms 41284 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, to_ans;
    while(n--) {
      int l, r; cin >> l >> r;
      pq.push({l, r});
    }
    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
0 / 10.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 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 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 398 ms 41284 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 433 ms 40512 KB Output is correct
3 Incorrect 431 ms 40836 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 433 ms 40512 KB Output is correct
3 Incorrect 431 ms 40836 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 433 ms 40512 KB Output is correct
3 Incorrect 431 ms 40836 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 40 ms 4936 KB Output is correct
3 Correct 41 ms 6928 KB Output is correct
4 Correct 418 ms 40944 KB Output is correct
5 Correct 42 ms 6928 KB Output is correct
6 Correct 40 ms 6964 KB Output is correct
7 Correct 46 ms 7124 KB Output is correct
8 Correct 43 ms 6984 KB Output is correct
9 Correct 43 ms 6940 KB Output is correct
10 Correct 42 ms 6964 KB Output is correct
11 Correct 42 ms 6984 KB Output is correct
12 Correct 42 ms 6972 KB Output is correct
13 Correct 42 ms 6956 KB Output is correct
14 Correct 413 ms 40836 KB Output is correct
15 Incorrect 43 ms 7868 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 5 ms 788 KB Output is correct
3 Correct 5 ms 1232 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -