oj.uz

Submission #719496

# Submission time Handle Problem Language Result Execution time Memory
719496 2023-04-06T06:12:16 Z keisuke6 Strange Device (APIO19_strange_device) C++17
65 / 100
 1900 ms 116848 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int N,A,B;
  cin>>N>>A>>B;
  B++;
  int g = gcd(A,B);
  B--;
  int p = 0;
  if(1.0*A*B/g >= 4e18) p = 2e18;
  else p = A*B/g;
  map<int,int> m;
  for(int i=0;i<N;i++){
    int l,r;
    cin>>l>>r;
    if(l == r){
      l %= p;
      r %= p;
      m[l]++;
      m[r+1]--;
      continue;
    }
    l %= p;
    r %= p;
    if(l >= r){
      m[l]++;
      m[p]--;
      m[0]++;
      m[r+1]--;
    }
    else{
      m[l]++;
      m[r+1]--;
    }
  }
  vector<pair<int,int>> S = {};
  for(auto x:m) S.push_back(x);
  sort(S.begin(),S.end());
  int now = S[0].second;
  int ans = 0;
  for(int i=1;i<S.size();i++){
    if(now){
      ans += S[i].first-S[i-1].first;
    }
    now += S[i].second;
  }
  cout<<ans<<endl;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:42:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for(int i=1;i<S.size();i++){
      |               ~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 17 ms 1240 KB Output is correct
3 Correct 15 ms 1240 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 15 ms 1220 KB Output is correct
17 Correct 155 ms 8692 KB Output is correct
18 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1547 ms 79512 KB Output is correct
3 Correct 1649 ms 116684 KB Output is correct
4 Correct 1693 ms 116744 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1547 ms 79512 KB Output is correct
3 Correct 1649 ms 116684 KB Output is correct
4 Correct 1693 ms 116744 KB Output is correct
5 Correct 0 ms 300 KB Output is correct
6 Correct 1633 ms 116848 KB Output is correct
7 Correct 1664 ms 116768 KB Output is correct
8 Correct 1618 ms 116672 KB Output is correct
9 Correct 1765 ms 116660 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1547 ms 79512 KB Output is correct
3 Correct 1649 ms 116684 KB Output is correct
4 Correct 1693 ms 116744 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 156 ms 12364 KB Output is correct
7 Correct 153 ms 12412 KB Output is correct
8 Correct 167 ms 12356 KB Output is correct
9 Correct 161 ms 12424 KB Output is correct
10 Correct 155 ms 12592 KB Output is correct
11 Correct 156 ms 12428 KB Output is correct
12 Correct 159 ms 12400 KB Output is correct
13 Correct 161 ms 12412 KB Output is correct
14 Correct 154 ms 12392 KB Output is correct
15 Correct 161 ms 12440 KB Output is correct
16 Correct 170 ms 12508 KB Output is correct
17 Correct 166 ms 12348 KB Output is correct
18 Correct 1634 ms 116752 KB Output is correct
19 Correct 1900 ms 116760 KB Output is correct
20 Correct 1767 ms 116668 KB Output is correct
21 Correct 158 ms 12460 KB Output is correct
22 Correct 162 ms 12452 KB Output is correct
23 Correct 416 ms 13060 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 162 ms 8676 KB Output is correct
3 Correct 169 ms 8664 KB Output is correct
4 Correct 1648 ms 79368 KB Output is correct
5 Correct 168 ms 8836 KB Output is correct
6 Correct 157 ms 8628 KB Output is correct
7 Correct 157 ms 8656 KB Output is correct
8 Correct 161 ms 8684 KB Output is correct
9 Correct 161 ms 8780 KB Output is correct
10 Correct 155 ms 8732 KB Output is correct
11 Correct 155 ms 8648 KB Output is correct
12 Correct 157 ms 8664 KB Output is correct
13 Correct 162 ms 8676 KB Output is correct
14 Correct 1683 ms 79468 KB Output is correct
15 Correct 153 ms 8788 KB Output is correct
16 Correct 1569 ms 79528 KB Output is correct
17 Correct 1552 ms 79524 KB Output is correct
18 Correct 0 ms 212 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 17 ms 1240 KB Output is correct
3 Correct 15 ms 1240 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 15 ms 1220 KB Output is correct
17 Correct 155 ms 8692 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Incorrect 1 ms 212 KB Output isn't correct
21 Halted 0 ms 0 KB -