oj.uz

Submission #719497

# Submission time Handle Problem Language Result Execution time Memory
719497 2023-04-06T06:20:18 Z keisuke6 Strange Device (APIO19_strange_device) C++17
65 / 100
 1666 ms 79692 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
signed main(){
  int N,A,B;
  cin>>N>>A>>B;
  B++;
  int g = gcd(A,B);
  B--;
  int p = 0;
  if((double)(1.0)*A*B/g >= 4e18) p = 2e18;
  else p = A/g*B;
  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:43: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]
   43 |   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 15 ms 1240 KB Output is correct
3 Correct 15 ms 1320 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 1 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 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 15 ms 1240 KB Output is correct
17 Correct 161 ms 8700 KB Output is correct
18 Correct 0 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 0 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 849 ms 284 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 1555 ms 79400 KB Output is correct
3 Correct 1601 ms 79504 KB Output is correct
4 Correct 1638 ms 79536 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 1555 ms 79400 KB Output is correct
3 Correct 1601 ms 79504 KB Output is correct
4 Correct 1638 ms 79536 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1625 ms 79524 KB Output is correct
7 Correct 1597 ms 79596 KB Output is correct
8 Correct 1588 ms 79436 KB Output is correct
9 Correct 1646 ms 79380 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 1555 ms 79400 KB Output is correct
3 Correct 1601 ms 79504 KB Output is correct
4 Correct 1638 ms 79536 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 155 ms 8780 KB Output is correct
7 Correct 150 ms 8748 KB Output is correct
8 Correct 155 ms 8732 KB Output is correct
9 Correct 157 ms 8660 KB Output is correct
10 Correct 149 ms 8772 KB Output is correct
11 Correct 149 ms 8664 KB Output is correct
12 Correct 154 ms 8716 KB Output is correct
13 Correct 158 ms 8724 KB Output is correct
14 Correct 152 ms 8672 KB Output is correct
15 Correct 159 ms 8644 KB Output is correct
16 Correct 158 ms 8740 KB Output is correct
17 Correct 158 ms 8792 KB Output is correct
18 Correct 1570 ms 79476 KB Output is correct
19 Correct 1605 ms 79636 KB Output is correct
20 Correct 1642 ms 79692 KB Output is correct
21 Correct 150 ms 8648 KB Output is correct
22 Correct 153 ms 8884 KB Output is correct
23 Correct 410 ms 272 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 165 ms 8652 KB Output is correct
3 Correct 164 ms 8672 KB Output is correct
4 Correct 1625 ms 79392 KB Output is correct
5 Correct 175 ms 8708 KB Output is correct
6 Correct 164 ms 8684 KB Output is correct
7 Correct 157 ms 8740 KB Output is correct
8 Correct 162 ms 8732 KB Output is correct
9 Correct 160 ms 8756 KB Output is correct
10 Correct 155 ms 8672 KB Output is correct
11 Correct 155 ms 8696 KB Output is correct
12 Correct 158 ms 8692 KB Output is correct
13 Correct 166 ms 8868 KB Output is correct
14 Correct 1666 ms 79380 KB Output is correct
15 Correct 149 ms 8704 KB Output is correct
16 Correct 1561 ms 79476 KB Output is correct
17 Correct 1556 ms 79456 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 15 ms 1240 KB Output is correct
3 Correct 15 ms 1320 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 1 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 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 15 ms 1240 KB Output is correct
17 Correct 161 ms 8700 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Incorrect 0 ms 212 KB Output isn't correct
21 Halted 0 ms 0 KB -