oj.uz

Submission #947000

# Submission time Handle Problem Language Result Execution time Memory
947000 2024-03-15T09:56:41 Z biximo Strange Device (APIO19_strange_device) C++17
5 / 100
 376 ms 73032 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);
    ll tp = (A/__gcd(A,B+1))*B;
    overs = (__int128)B*(A/__gcd(A,B+1)) <= 1e18;
    for(auto&[l,r]: seq) {
    	cin >> l >> r;
    }
    if(overs) {
    	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 = A*B-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 1 ms 604 KB Output is correct
2 Correct 4 ms 860 KB Output is correct
3 Runtime error 4 ms 1092 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 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 1 ms 348 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 358 ms 53200 KB Output is correct
3 Runtime error 257 ms 73032 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 358 ms 53200 KB Output is correct
3 Runtime error 257 ms 73032 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 358 ms 53200 KB Output is correct
3 Runtime error 257 ms 73032 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 0 ms 348 KB Output is correct
2 Correct 35 ms 5472 KB Output is correct
3 Correct 35 ms 5592 KB Output is correct
4 Correct 376 ms 53204 KB Output is correct
5 Correct 35 ms 5712 KB Output is correct
6 Correct 34 ms 5580 KB Output is correct
7 Correct 40 ms 5712 KB Output is correct
8 Correct 39 ms 5580 KB Output is correct
9 Correct 35 ms 5580 KB Output is correct
10 Correct 34 ms 5468 KB Output is correct
11 Correct 40 ms 5724 KB Output is correct
12 Runtime error 30 ms 7360 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 1 ms 604 KB Output is correct
2 Correct 4 ms 860 KB Output is correct
3 Runtime error 4 ms 1092 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -