Submission #346636

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
346636	2021-01-10T13:50:13 Z	YJU	Strange Device (APIO19_strange_device)	C++14	65 / 100	520 ms	27020 KB

strange_device

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=2e5+5;
const ld pi=acos(-1);
const ll INF=1e18;
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

ll n,a,b,ans,last,x,y;
vector<pll> v;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>a>>b;
	ll g=__gcd(a,b+1);
	if(a/g>=INF/b){
		REP(i,n)cin>>x>>y,ans+=y-x+1;
		cout<<ans<<"\n";return 0;
	}
	ll ab=(a/g*b);
	REP(i,n){
		cin>>x>>y;
		x%=ab;y%=ab;
		if(x>y){
			v.pb(mp(x,ab));
			v.pb(mp(0,y+1));
		}else{
			v.pb(mp(x,y+1));
		}
	}
	sort(v.begin(),v.end());
	for(auto i:v){
		ans+=max(0LL,i.Y-max(last,i.X));
		last=max(last,i.Y);
	}
	cout<<min(ans,ab)<<"\n";
	return 0;
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	5 ms	748 KB	Output is correct
3	Correct	5 ms	1132 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	384 KB	Output is correct
16	Correct	5 ms	1132 KB	Output is correct
17	Correct	51 ms	5752 KB	Output is correct
18	Correct	0 ms	364 KB	Output is correct

Subtask #2
0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	364 KB	Output is correct
2	Incorrect	364 KB	Output isn't correct
3	Halted	0 KB	-

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	334 ms	23632 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	446 ms	16848 KB	Output is correct
3	Correct	464 ms	26956 KB	Output is correct
4	Correct	440 ms	26832 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	446 ms	16848 KB	Output is correct
3	Correct	464 ms	26956 KB	Output is correct
4	Correct	440 ms	26832 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	453 ms	26888 KB	Output is correct
7	Correct	460 ms	27004 KB	Output is correct
8	Correct	446 ms	26832 KB	Output is correct
9	Correct	491 ms	26960 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	446 ms	16848 KB	Output is correct
3	Correct	464 ms	26956 KB	Output is correct
4	Correct	440 ms	26832 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	45 ms	5732 KB	Output is correct
7	Correct	49 ms	5732 KB	Output is correct
8	Correct	47 ms	5732 KB	Output is correct
9	Correct	46 ms	5732 KB	Output is correct
10	Correct	45 ms	5732 KB	Output is correct
11	Correct	47 ms	5732 KB	Output is correct
12	Correct	44 ms	5732 KB	Output is correct
13	Correct	48 ms	5732 KB	Output is correct
14	Correct	45 ms	5732 KB	Output is correct
15	Correct	50 ms	5732 KB	Output is correct
16	Correct	49 ms	5732 KB	Output is correct
17	Correct	49 ms	5808 KB	Output is correct
18	Correct	452 ms	26920 KB	Output is correct
19	Correct	445 ms	26832 KB	Output is correct
20	Correct	500 ms	26984 KB	Output is correct
21	Correct	49 ms	5732 KB	Output is correct
22	Correct	44 ms	5732 KB	Output is correct
23	Correct	145 ms	18524 KB	Output is correct

Subtask #7
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	47 ms	2664 KB	Output is correct
3	Correct	51 ms	5860 KB	Output is correct
4	Correct	520 ms	26872 KB	Output is correct
5	Correct	47 ms	5732 KB	Output is correct
6	Correct	49 ms	5732 KB	Output is correct
7	Correct	48 ms	5732 KB	Output is correct
8	Correct	49 ms	5752 KB	Output is correct
9	Correct	47 ms	5732 KB	Output is correct
10	Correct	48 ms	5732 KB	Output is correct
11	Correct	49 ms	5732 KB	Output is correct
12	Correct	43 ms	5732 KB	Output is correct
13	Correct	49 ms	5752 KB	Output is correct
14	Correct	493 ms	27020 KB	Output is correct
15	Correct	49 ms	5732 KB	Output is correct
16	Correct	446 ms	26832 KB	Output is correct
17	Correct	442 ms	26832 KB	Output is correct
18	Correct	1 ms	492 KB	Output is correct

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	5 ms	748 KB	Output is correct
3	Correct	5 ms	1132 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	384 KB	Output is correct
16	Correct	5 ms	1132 KB	Output is correct
17	Correct	51 ms	5752 KB	Output is correct
18	Correct	0 ms	364 KB	Output is correct
19	Correct	0 ms	364 KB	Output is correct
20	Incorrect	0 ms	364 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Submission #346636

Compilation message