oj.uz

Submission #698851

# Submission time Handle Problem Language Result Execution time Memory
698851 2023-02-14T13:30:30 Z Abrar_Al_Samit Strange Device (APIO19_strange_device) C++17
15 / 100
 721 ms 115812 KB 
#include<bits/stdc++.h>
using namespace std;

long long gcd(long long x, long long y) {
    if (y == 0) return x;
    return gcd(y, x%y);
}
void PlayGround() {
  long long n, a, b;
  cin>>n>>a>>b;

  vector<array<long long,2>>iner(n);
  for(int i=0; i<n; ++i) {
    cin>>iner[i][0]>>iner[i][1];
  }

  long long g = gcd(a, b+1);
  long long interval = (a / gcd(a, b+1));
  bool toobig = false;
  if(log10(interval)+log10(b)>18) {
    toobig = true;
  } else {
    interval *= b;
  }

  for(int i=0; i<n; ++i) {
    long long len = iner[i][1] - iner[i][0] + 1;
    if(!toobig && len>=interval) {
      cout<<interval<<'\n';
      return;
    }
  }

  set<pair<long long, long long>>s;


  for(int i=0; i<n; ++i) {
    long long len = iner[i][1]-iner[i][0]+1;
    long long l = iner[i][0]%interval;
    long long r = iner[i][1]%interval;
    if(!toobig) {
      if(l>r) {
        s.insert({l, interval-1});
        s.insert({0, r});
      } else {
        s.insert({l, r});
      }
    } else {
      s.insert({l, r});
    }
  }

  long long ans = 0;
  while(!s.empty()) {
    auto it = s.begin();
    s.erase(it);
    long long l = it->first, r = it->second;
    if(!s.empty()) {
      auto nx = s.upper_bound(*it);
      r = min(r, nx->first-1);
    }
    ans += r-l+1;
  }
  cout<<ans<<'\n';

  // cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  PlayGround();
  return 0;
}

Compilation message

strange_device.cpp: In function 'void PlayGround()':
strange_device.cpp:38:15: warning: unused variable 'len' [-Wunused-variable]
   38 |     long long len = iner[i][1]-iner[i][0]+1;
      |               ^~~
strange_device.cpp:17:13: warning: unused variable 'g' [-Wunused-variable]
   17 |   long long g = gcd(a, b+1);
      |             ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 5 ms 996 KB Output isn't correct
3 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 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #3
0 / 5.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 516 ms 78572 KB Output is correct
3 Correct 593 ms 115584 KB Output is correct
4 Correct 619 ms 115660 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 516 ms 78572 KB Output is correct
3 Correct 593 ms 115584 KB Output is correct
4 Correct 619 ms 115660 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 571 ms 115624 KB Output is correct
7 Correct 603 ms 115664 KB Output is correct
8 Correct 565 ms 115812 KB Output is correct
9 Correct 688 ms 115668 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 516 ms 78572 KB Output is correct
3 Correct 593 ms 115584 KB Output is correct
4 Correct 619 ms 115660 KB Output is correct
5 Correct 0 ms 324 KB Output is correct
6 Correct 51 ms 11852 KB Output is correct
7 Correct 52 ms 11864 KB Output is correct
8 Correct 52 ms 11852 KB Output is correct
9 Correct 56 ms 11868 KB Output is correct
10 Correct 55 ms 11988 KB Output is correct
11 Correct 51 ms 11864 KB Output is correct
12 Correct 50 ms 11980 KB Output is correct
13 Correct 57 ms 11856 KB Output is correct
14 Correct 51 ms 11848 KB Output is correct
15 Incorrect 56 ms 11800 KB Output isn't correct
16 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 60 ms 8016 KB Output is correct
3 Correct 56 ms 11848 KB Output is correct
4 Correct 591 ms 115780 KB Output is correct
5 Correct 58 ms 11852 KB Output is correct
6 Correct 58 ms 11860 KB Output is correct
7 Correct 57 ms 11852 KB Output is correct
8 Correct 58 ms 11852 KB Output is correct
9 Correct 59 ms 11968 KB Output is correct
10 Correct 52 ms 11848 KB Output is correct
11 Correct 54 ms 11864 KB Output is correct
12 Correct 54 ms 11764 KB Output is correct
13 Correct 57 ms 11856 KB Output is correct
14 Incorrect 721 ms 115680 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

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