oj.uz

Submission #409811

# Submission time Handle Problem Language Result Execution time Memory
409811 2021-05-21T15:18:43 Z kwongweng Strange Device (APIO19_strange_device) C++17
65 / 100
 571 ms 35388 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define F first
#define S second
ll MOD = 1000000007;
ll INF = 1000000000;
 
ll power(ll base, ll n){
	if (n == 0) return 1;
	if (n == 1) return base;
	ll halfn = power(base, n/2);
	if (n % 2 == 0) return (halfn * halfn) % MOD;
	return (((halfn * halfn) % MOD) * base) % MOD;
}
 
ll inverse(ll n){
	return power(n, MOD-2);
}
 
ll add(ll a, ll b){
	return (a+b) % MOD;
}
 
ll mul(ll a, ll b){
	return (a*b) % MOD;
}
 
ll gcd(ll a, ll b){
	if (a == 0) return b;
	if (a == 1) return 1;
	return gcd(b%a, a);
}

int check(ll n){
	ll m = n;
	int cnt = 0;
	while (m > 0){
		m /= 2;
		cnt++;
	}
	return cnt;
}
ll len = MOD*MOD;
int main(){
    ios::sync_with_stdio(false);
    int n; cin >> n;
    ll a, b; cin >> a >> b;
    ll c = a / gcd(a, b+1);
    if (check(b) + check(c) < 63){
    	len = b*c;
	}
	vector<pll> range;
	FOR(i, 0, n){
		ll l, r; cin >> l >> r;
		l%=len; r%=len;
		if (l > r){
			range.pb({0, r%len});
			range.pb({l%len, len-1});
		}else{
			range.pb({l, r});
		}
	}
	sort(range.begin(), range.end());
	ll ans = 0;
	ll l = range[0].F; ll r = range[0].S;
	FOR(i, 0, range.size()){
		if (range[i].F - r > 1){
			ans += r - l + 1;
			l = range[i].F; r = range[i].S;
			continue;
		}
		r = max(range[i].S, r);
	}
	ans += r - l + 1;
	cout << ans << '\n';
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:9:39: 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]
    9 | #define FOR(i, a, b) for(int i = a; i < b; i++)
......
   76 |  FOR(i, 0, range.size()){
      |      ~~~~~~~~~~~~~~~~~~                
strange_device.cpp:76:2: note: in expansion of macro 'FOR'
   76 |  FOR(i, 0, range.size()){
      |  ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 6 ms 976 KB Output is correct
3 Correct 7 ms 976 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 6 ms 976 KB Output is correct
17 Correct 55 ms 3100 KB Output is correct
18 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 389 ms 19540 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 504 ms 16940 KB Output is correct
3 Correct 510 ms 17892 KB Output is correct
4 Correct 497 ms 18084 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 504 ms 16940 KB Output is correct
3 Correct 510 ms 17892 KB Output is correct
4 Correct 497 ms 18084 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 490 ms 17952 KB Output is correct
7 Correct 513 ms 25572 KB Output is correct
8 Correct 498 ms 25944 KB Output is correct
9 Correct 546 ms 25824 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 504 ms 16940 KB Output is correct
3 Correct 510 ms 17892 KB Output is correct
4 Correct 497 ms 18084 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 49 ms 5628 KB Output is correct
7 Correct 52 ms 5696 KB Output is correct
8 Correct 69 ms 5608 KB Output is correct
9 Correct 55 ms 5596 KB Output is correct
10 Correct 51 ms 5624 KB Output is correct
11 Correct 52 ms 5688 KB Output is correct
12 Correct 54 ms 5684 KB Output is correct
13 Correct 52 ms 5648 KB Output is correct
14 Correct 49 ms 5692 KB Output is correct
15 Correct 74 ms 5632 KB Output is correct
16 Correct 53 ms 5624 KB Output is correct
17 Correct 50 ms 5696 KB Output is correct
18 Correct 523 ms 18096 KB Output is correct
19 Correct 492 ms 35324 KB Output is correct
20 Correct 550 ms 35344 KB Output is correct
21 Correct 54 ms 5652 KB Output is correct
22 Correct 52 ms 5600 KB Output is correct
23 Correct 168 ms 18376 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 53 ms 4640 KB Output is correct
3 Correct 54 ms 4628 KB Output is correct
4 Correct 571 ms 16884 KB Output is correct
5 Correct 53 ms 4664 KB Output is correct
6 Correct 53 ms 4612 KB Output is correct
7 Correct 52 ms 4640 KB Output is correct
8 Correct 54 ms 4668 KB Output is correct
9 Correct 53 ms 4648 KB Output is correct
10 Correct 53 ms 4680 KB Output is correct
11 Correct 70 ms 4664 KB Output is correct
12 Correct 48 ms 4656 KB Output is correct
13 Correct 53 ms 4708 KB Output is correct
14 Correct 538 ms 17012 KB Output is correct
15 Correct 53 ms 4708 KB Output is correct
16 Correct 507 ms 35240 KB Output is correct
17 Correct 506 ms 35388 KB Output is correct
18 Correct 1 ms 204 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 6 ms 976 KB Output is correct
3 Correct 7 ms 976 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 6 ms 976 KB Output is correct
17 Correct 55 ms 3100 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Incorrect 1 ms 308 KB Output isn't correct
21 Halted 0 ms 0 KB -