oj.uz

Submission #266429

# Submission time Handle Problem Language Result Execution time Memory
266429 2020-08-15T09:19:52 Z define Strange Device (APIO19_strange_device) C++17
10 / 100
 3365 ms 65084 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define len(s) (int)s.size()
 
template<class T> inline bool chmin(T &a, T b){
	if(a>b){a=b;return true;}
	return false;
}
template<class T> inline bool chmax(T &a, T b){
	if(a<b){a=b;return true;}
	return false;
}
constexpr int mod = 1e9+7;
constexpr long long inf = 3e18;

int gcd(int x,int y){
	return (y?gcd(y,x%y):x);
}
int A,B,N;
void solve1(){
	int ans=0;
	while(N--){
		int a,b;cin>>a>>b;
		ans+=b-a+1;
	}
	cout<<ans<<endl;
	exit(0);
}
signed main(){
	cin>>N>>A>>B;
	int x=(A%B+1)%A;
	int g=gcd(A,x);
	if(inf/(A/g)<B)solve1();
	int lc=A/g*B;
	set<P>st;
	rep(i,N){
		int a,b;cin>>a>>b;
		if(b-a+1>=lc){
			cout<<lc<<endl;return 0;
		}
		if(a/lc!=b/lc){
			st.insert({a%lc,lc-1});
			st.insert({0,b%lc});
		}else {
			st.insert({a%lc,b%lc});
		}
	}
	int ans=0,now=-1;
	for(P i:st){
		if(i.first<=now){
			ans+=max(0ll,i.second-now);
			chmax(now,i.second);
		}else {
			ans+=i.second-i.first+1;
			now=i.second;
		}
	}
	cout<<ans<<endl;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 33 ms 1272 KB Output is correct
3 Correct 32 ms 1272 KB Output is correct
4 Incorrect 0 ms 256 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 2098 ms 3320 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 3258 ms 65084 KB Output is correct
3 Incorrect 3267 ms 65016 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 3258 ms 65084 KB Output is correct
3 Incorrect 3267 ms 65016 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 3258 ms 65084 KB Output is correct
3 Incorrect 3267 ms 65016 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 327 ms 7544 KB Output is correct
3 Correct 326 ms 7416 KB Output is correct
4 Correct 3365 ms 64752 KB Output is correct
5 Correct 323 ms 7416 KB Output is correct
6 Correct 323 ms 7416 KB Output is correct
7 Correct 326 ms 7416 KB Output is correct
8 Correct 319 ms 7416 KB Output is correct
9 Correct 324 ms 7544 KB Output is correct
10 Correct 318 ms 7416 KB Output is correct
11 Correct 328 ms 7416 KB Output is correct
12 Correct 322 ms 7416 KB Output is correct
13 Correct 326 ms 7416 KB Output is correct
14 Correct 3280 ms 64880 KB Output is correct
15 Incorrect 325 ms 7288 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 33 ms 1272 KB Output is correct
3 Correct 32 ms 1272 KB Output is correct
4 Incorrect 0 ms 256 KB Output isn't correct
5 Halted 0 ms 0 KB -