oj.uz

Submission #678131

# Submission time Handle Problem Language Result Execution time Memory
678131 2023-01-05T08:39:29 Z faribourz Strange Device (APIO19_strange_device) C++14
30 / 100
 805 ms 66444 KB 
// Only GOD
// believe in yourself
// Nemidam Del Be In Darde Donya!
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define bit(x, y) ((x >> y)&1)
#define sz(x) (int)x.size()
#define kill(x) return cout << x << '\n', void()
#define KILL(x) return cout << x << '\n', 0
#define int ll
const int N = 2e5+10;
const int INF = 1e18+10;
map<int, int> M;
int32_t main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int A, B, n;
	cin >> n >> A >> B;
	int g = __gcd(A, B+1);
	int AB;
	A /= g;
	if(INF / A < B){
		AB = INF;
	}
	else
		AB = A*B;
	int ans = 0;
	for(int i = 0; i < n; i++){
		int l, r;
		cin >> l >> r;
		if(r-l+1 >= AB)
			ans = AB;
		l %= AB, r %= AB;
		if(!r){
			M[l]++;
			M[0]++;
			M[1]--;
			continue;
		}
		if(l <= r){
			M[l]++;
			M[r+1]--;
		}
		else{
			M[0]++;
			M[l]++;
			M[r+1]--;
		}
	}
	if(ans)
		KILL(ans);
	if(!M.count(AB))
		M[AB] = 0;
	int sum = 0, lst = -1;
	ans = 0;
	for(auto x : M){
		if(lst == -1){
			sum += x.S;
			lst = x.F;
			continue;
		}
		if(sum > 0){
			ans += x.F-lst;
		}
		sum += x.S;
		lst = x.F;
	}
	cout << ans;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 6 ms 1268 KB Output is correct
3 Correct 9 ms 1236 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Incorrect 1 ms 212 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 243 ms 1788 KB Output is correct

Subtask #4
0 / 5.0

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 711 ms 66444 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 1 ms 212 KB Output is correct
2 Correct 66 ms 9400 KB Output is correct
3 Correct 70 ms 9932 KB Output is correct
4 Correct 678 ms 64568 KB Output is correct
5 Correct 67 ms 9892 KB Output is correct
6 Correct 67 ms 9928 KB Output is correct
7 Correct 67 ms 9912 KB Output is correct
8 Correct 65 ms 9984 KB Output is correct
9 Correct 64 ms 9892 KB Output is correct
10 Correct 71 ms 9932 KB Output is correct
11 Correct 61 ms 9964 KB Output is correct
12 Correct 61 ms 9912 KB Output is correct
13 Correct 69 ms 9976 KB Output is correct
14 Correct 805 ms 64588 KB Output is correct
15 Correct 59 ms 9932 KB Output is correct
16 Correct 636 ms 64520 KB Output is correct
17 Correct 627 ms 64528 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 324 KB Output is correct
2 Correct 6 ms 1268 KB Output is correct
3 Correct 9 ms 1236 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Incorrect 1 ms 212 KB Output isn't correct
11 Halted 0 ms 0 KB -