oj.uz

Submission #947003

# Submission time Handle Problem Language Result Execution time Memory
947003 2024-03-15T09:58:12 Z biximo Strange Device (APIO19_strange_device) C++17
5 / 100
 397 ms 52956 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef array<ll, 2> p2;
int n;
ll A,B;
vector<p2> seq;
bool overs;
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> A >> B;
    seq.resize(n);
    overs = (__int128)B*(A/__gcd(A,B+1)) <= 1e18;
    for(auto&[l,r]: seq) {
    	cin >> l >> r;
    }
    if(overs) {
    	ll tp = (A/__gcd(A,B+1))*B;
    	for(int i = 0; i < n; i ++) {
    		auto&[l,r] = seq[i];
    		if(r-l+1>=tp) {
    			cout << tp;
    			return 0;
    		}
    		if(l%tp > r%tp) {
    			seq.push_back({0,r%tp});
    			l %= tp;
    			r = tp-1;
    		} else {
    			l %= tp;
    			r %= tp;
    		}
    	}
    }
    sort(seq.begin(),seq.end());
    ll L = -1, R = -2, ans = 0;
    for(auto[l,r]: seq) {
    	if(l <= R+1) {
    		R = max(R, r);
    	} else {
    		ans += R-L+1;
    		L = l;
    		R = r;
    	}
    }
    ans += R-L+1;
    cout << ans;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 4 ms 860 KB Output is correct
3 Runtime error 4 ms 1208 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Correct 1 ms 528 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 5.0

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

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 342 ms 34652 KB Output is correct
3 Runtime error 271 ms 52956 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 342 ms 34652 KB Output is correct
3 Runtime error 271 ms 52956 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 342 ms 34652 KB Output is correct
3 Runtime error 271 ms 52956 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 37 ms 3912 KB Output is correct
3 Correct 40 ms 3904 KB Output is correct
4 Correct 397 ms 34624 KB Output is correct
5 Correct 35 ms 3928 KB Output is correct
6 Correct 40 ms 3932 KB Output is correct
7 Correct 38 ms 3952 KB Output is correct
8 Correct 34 ms 3924 KB Output is correct
9 Correct 33 ms 3932 KB Output is correct
10 Correct 34 ms 3932 KB Output is correct
11 Correct 34 ms 3932 KB Output is correct
12 Runtime error 28 ms 6968 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 4 ms 860 KB Output is correct
3 Runtime error 4 ms 1208 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -