oj.uz

Submission #598910

# Submission time Handle Problem Language Result Execution time Memory
598910 2022-07-19T07:34:23 Z sentheta Strange Device (APIO19_strange_device) C++17
5 / 100
 2802 ms 524288 KB 
// author : sentheta aka vanwij
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<random>
#include<chrono>
#include<cmath>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

#define rand() (uniform_int_distribution<int>(0,1<<30)(rng))
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;

#define int long long
const Int MOD = 1e9+7;
//const Int MOD = 998244353;
Int bpow(Int a,Int b){
	Int ret = 1;
	for(;b; a=a*a%MOD,b/=2) if(b&1) ret = ret*a%MOD;
	return ret;
}
Int inv(Int a){return bpow(a,MOD-2);}

void solve(); int TC;
signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	srand(chrono::steady_clock::now().time_since_epoch().count());
	cout << fixed << setprecision(7);
///cin >> TC; while(TC--) solve(); return 0;
	solve();
}





int n;
int A, B;
int len;

pii f(int x){
	return {(x+x/B)%A, x%B};
}


void solve(){
	


	cin >> n >> A >> B;

	if(A/gcd(A,B+1)*((double)(B)) > 1e18+5){
		len = 1e18+5;
	}
	else len = A/gcd(A,B+1)*B;

	//dbg(len);
	set<pii> s;
	rep(i,0,len) s.insert(f(i));
	assert((int)s.size()==len);
	rep(i,len,1e7) assert(f(i)==f(i-len));
	//return;

	priority_queue<pii> pq;

	rep(i,0,n){
		int l, r;
		cin >> l >> r;

		if(r-l+1 >= len){
			cout << len << nl; return;
		}
		l %= len; r %= len;

		if(l <= r){
			pq.push({-l, r});
		}
		else{
			pq.push({-l, len-1});
			pq.push({0, r});
		}
	}
	
	int ans = 0;

	int l = -1, r = -2;
	while(!pq.empty()){
		auto[tl,tr] = pq.top(); pq.pop();
		tl *= -1;
		//cout << tl _ tr << nl;

		if(r < tl){
			ans += r-l+1;

			l = tl; r = tr;
		}
		else{
			r = max(r, tr);
		}
	}
	ans += r-l+1;

	cout << ans << nl;
	
	
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 300 KB Output is correct
2 Correct 1966 ms 405840 KB Output is correct
3 Correct 1734 ms 311508 KB Output is correct
4 Correct 283 ms 1420 KB Output is correct
5 Correct 303 ms 372 KB Output is correct
6 Correct 310 ms 324 KB Output is correct
7 Correct 300 ms 668 KB Output is correct
8 Correct 307 ms 468 KB Output is correct
9 Correct 307 ms 1108 KB Output is correct
10 Correct 342 ms 304 KB Output is correct
11 Correct 325 ms 308 KB Output is correct
12 Correct 317 ms 312 KB Output is correct
13 Correct 326 ms 340 KB Output is correct
14 Correct 304 ms 376 KB Output is correct
15 Correct 307 ms 7916 KB Output is correct
16 Correct 317 ms 12740 KB Output is correct
17 Correct 815 ms 129488 KB Output is correct
18 Runtime error 2540 ms 524288 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 304 KB Output is correct
2 Runtime error 2541 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 304 KB Output is correct
2 Correct 421 ms 60648 KB Output is correct
3 Correct 522 ms 61444 KB Output is correct
4 Correct 424 ms 51068 KB Output is correct
5 Correct 875 ms 103708 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 304 KB Output is correct
2 Correct 998 ms 130448 KB Output is correct
3 Runtime error 2802 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 304 KB Output is correct
2 Correct 998 ms 130448 KB Output is correct
3 Runtime error 2802 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 304 KB Output is correct
2 Correct 998 ms 130448 KB Output is correct
3 Runtime error 2802 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 308 KB Output is correct
2 Runtime error 1427 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 300 KB Output is correct
2 Correct 1966 ms 405840 KB Output is correct
3 Correct 1734 ms 311508 KB Output is correct
4 Correct 283 ms 1420 KB Output is correct
5 Correct 303 ms 372 KB Output is correct
6 Correct 310 ms 324 KB Output is correct
7 Correct 300 ms 668 KB Output is correct
8 Correct 307 ms 468 KB Output is correct
9 Correct 307 ms 1108 KB Output is correct
10 Correct 342 ms 304 KB Output is correct
11 Correct 325 ms 308 KB Output is correct
12 Correct 317 ms 312 KB Output is correct
13 Correct 326 ms 340 KB Output is correct
14 Correct 304 ms 376 KB Output is correct
15 Correct 307 ms 7916 KB Output is correct
16 Correct 317 ms 12740 KB Output is correct
17 Correct 815 ms 129488 KB Output is correct
18 Runtime error 2540 ms 524288 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -