oj.uz

Submission #1107608

# Submission time Handle Problem Language Result Execution time Memory
1107608 2024-11-01T17:04:49 Z arnavsrivastava0123 Strange Device (APIO19_strange_device) C++17
35 / 100
 327 ms 54304 KB 
#include <bits/stdc++.h>

using namespace std;

const long long INF = 1e18 + 7;
 
void solve(){
   long long n, A, B; cin >> n >> A >> B;
   A = A / gcd(A, B + 1);
   if(A > INF / B){
      cout << 0 << '\n';
      return;
   }
   long long MOD = A * B;
   long long ans = 0;
   vector<pair<long long, long long>> intervals;
   for(int i = 0; i < n;i++){
      long long L, R; cin >> L >> R;
      if(L / MOD == R / MOD){
        intervals.push_back({L % MOD, R % MOD});
      }else if(L / MOD + 1 == R / MOD){
        intervals.push_back({L % MOD, MOD - 1});
        intervals.push_back({0, R % MOD});
      }else if(R / MOD >= L / MOD + 2){
        cout << MOD << '\n';
        return;
      }
   }
   sort(intervals.begin(), intervals.end());
   long long last = intervals[0].second + 1;
   ans = intervals[0].second - intervals[0].first + 1;
   for(int i = 1; i < intervals.size();i++){
      ans += max(0LL, intervals[i].second - max(intervals[i].first, last) + 1);
      last = max(last, intervals[i].second + 1);
   }
   cout << ans << '\n';
}
 
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
 
int T = 1; //cin >> T;
while(T--){
  solve();
}
}
/*
how many unique  pairs (t + t / B % A, t % B)

*/

Compilation message

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 4 ms 1104 KB Output is correct
3 Correct 6 ms 1236 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 4 ms 1104 KB Output is correct
17 Correct 30 ms 6344 KB Output is correct
18 Incorrect 1 ms 336 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 508 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Incorrect 1 ms 336 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 195 ms 42160 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 273 ms 54084 KB Output is correct
3 Correct 263 ms 54068 KB Output is correct
4 Correct 282 ms 53940 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 273 ms 54084 KB Output is correct
3 Correct 263 ms 54068 KB Output is correct
4 Correct 282 ms 53940 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 278 ms 53920 KB Output is correct
7 Correct 278 ms 54060 KB Output is correct
8 Correct 259 ms 54304 KB Output is correct
9 Correct 298 ms 54100 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 273 ms 54084 KB Output is correct
3 Correct 263 ms 54068 KB Output is correct
4 Correct 282 ms 53940 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 26 ms 6264 KB Output is correct
7 Correct 29 ms 6336 KB Output is correct
8 Correct 26 ms 6344 KB Output is correct
9 Correct 28 ms 6348 KB Output is correct
10 Correct 26 ms 6136 KB Output is correct
11 Correct 28 ms 6348 KB Output is correct
12 Correct 27 ms 6336 KB Output is correct
13 Correct 30 ms 6340 KB Output is correct
14 Correct 26 ms 6336 KB Output is correct
15 Correct 32 ms 6352 KB Output is correct
16 Correct 29 ms 6088 KB Output is correct
17 Correct 28 ms 6360 KB Output is correct
18 Correct 257 ms 54184 KB Output is correct
19 Correct 254 ms 53940 KB Output is correct
20 Correct 303 ms 53916 KB Output is correct
21 Correct 30 ms 6344 KB Output is correct
22 Correct 31 ms 6096 KB Output is correct
23 Correct 88 ms 20664 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 39 ms 6336 KB Output is correct
3 Correct 32 ms 6228 KB Output is correct
4 Correct 299 ms 54192 KB Output is correct
5 Correct 34 ms 6348 KB Output is correct
6 Correct 31 ms 6348 KB Output is correct
7 Correct 35 ms 6348 KB Output is correct
8 Correct 30 ms 6348 KB Output is correct
9 Correct 30 ms 6352 KB Output is correct
10 Correct 30 ms 6348 KB Output is correct
11 Correct 31 ms 6208 KB Output is correct
12 Correct 28 ms 6336 KB Output is correct
13 Correct 41 ms 6348 KB Output is correct
14 Correct 327 ms 53940 KB Output is correct
15 Correct 30 ms 6336 KB Output is correct
16 Correct 277 ms 54184 KB Output is correct
17 Correct 287 ms 53932 KB Output is correct
18 Incorrect 1 ms 508 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 4 ms 1104 KB Output is correct
3 Correct 6 ms 1236 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 4 ms 1104 KB Output is correct
17 Correct 30 ms 6344 KB Output is correct
18 Incorrect 1 ms 336 KB Output isn't correct
19 Halted 0 ms 0 KB -