oj.uz

Submission #719494

# Submission time Handle Problem Language Result Execution time Memory
719494 2023-04-06T06:09:31 Z keisuke6 Strange Device (APIO19_strange_device) C++17
25 / 100
 1853 ms 116740 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){
      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:40: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]
   40 |   for(int i=1;i<S.size();i++){
      |               ~^~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 16 ms 1328 KB Output is correct
3 Correct 16 ms 1312 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 Incorrect 0 ms 212 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 2 ms 340 KB Output is correct
4 Correct 3 ms 328 KB Output is correct
5 Correct 918 ms 25356 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 Incorrect 1737 ms 79388 KB Output isn't correct
3 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 Incorrect 1737 ms 79388 KB Output isn't correct
3 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 Incorrect 1737 ms 79388 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 176 ms 12380 KB Output is correct
3 Correct 203 ms 12368 KB Output is correct
4 Correct 1835 ms 116624 KB Output is correct
5 Correct 179 ms 12444 KB Output is correct
6 Correct 168 ms 12528 KB Output is correct
7 Correct 187 ms 12452 KB Output is correct
8 Correct 178 ms 12416 KB Output is correct
9 Correct 166 ms 12496 KB Output is correct
10 Correct 162 ms 12432 KB Output is correct
11 Correct 164 ms 12356 KB Output is correct
12 Correct 162 ms 12368 KB Output is correct
13 Correct 163 ms 12460 KB Output is correct
14 Correct 1853 ms 116740 KB Output is correct
15 Correct 157 ms 12364 KB Output is correct
16 Correct 1669 ms 116564 KB Output is correct
17 Correct 1666 ms 116724 KB Output is correct
18 Correct 1 ms 212 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 16 ms 1328 KB Output is correct
3 Correct 16 ms 1312 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 Incorrect 0 ms 212 KB Output isn't correct
11 Halted 0 ms 0 KB -