Submission #335109

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
335109	2020-12-11T07:22:13 Z	CSQ31	Strange Device (APIO19_strange_device)	C++17	65 / 100	1526 ms	17632 KB

strange_device

#pragma GCC optimize("Ofast") 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define all(a) a.begin(),a.end()
#define sz(a) (int)(a.size())
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(1e9+7)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll A,ll B) {if(!B)return A;return gcd(B,A%B);}
int main()
{
	ll n,a,b;
	cin>>n>>a>>b;
	ll C = (a*b)/gcd(a,b+1);
	//cout<<C<<'\n';
	vector<PII>s;
	for(int i=0;i<n;i++){
		ll l,r;
		cin>>l>>r;
		l%=C;
		r%=C;
		if(r >= l){
			s.pb({l,r});
		}else{
			s.pb({l,C-1});
			s.pb({0,r});
		}
	}
	sort(all(s));
	ll ans = 0;
	ll lf = 0;
	ll rg = -1;
	for(int i=0;i<sz(s);i++){
		//cout<<s[i].fi<<" "<<s[i].se<<'\n';
		if(s[i].fi > rg){
			ans+=rg-lf+1;
			lf = s[i].fi;
			rg = s[i].se;
			if(i == sz(s)-1)ans+=rg-lf+1;
		}else{
			rg = max(rg,s[i].se);
			if(i == sz(s)-1)ans+=rg-lf+1;
		}
		//cout<<ans<<'\n';
	}
	cout<<ans<<'\n';
	
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	15 ms	876 KB	Output is correct
3	Correct	15 ms	876 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	364 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	364 KB	Output is correct
16	Correct	15 ms	876 KB	Output is correct
17	Correct	150 ms	2912 KB	Output is correct
18	Correct	1 ms	364 KB	Output is correct

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Incorrect	1 ms	364 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	364 KB	Output is correct
2	Correct	2 ms	364 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	2 ms	364 KB	Output is correct
5	Correct	1041 ms	17156 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1466 ms	17308 KB	Output is correct
3	Correct	1452 ms	17096 KB	Output is correct
4	Correct	1445 ms	17096 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1466 ms	17308 KB	Output is correct
3	Correct	1452 ms	17096 KB	Output is correct
4	Correct	1445 ms	17096 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1456 ms	17384 KB	Output is correct
7	Correct	1461 ms	17096 KB	Output is correct
8	Correct	1446 ms	17488 KB	Output is correct
9	Correct	1510 ms	17096 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1466 ms	17308 KB	Output is correct
3	Correct	1452 ms	17096 KB	Output is correct
4	Correct	1445 ms	17096 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	147 ms	5212 KB	Output is correct
7	Correct	149 ms	5216 KB	Output is correct
8	Correct	148 ms	5216 KB	Output is correct
9	Correct	146 ms	5236 KB	Output is correct
10	Correct	146 ms	5216 KB	Output is correct
11	Correct	149 ms	5216 KB	Output is correct
12	Correct	146 ms	5216 KB	Output is correct
13	Correct	153 ms	5212 KB	Output is correct
14	Correct	146 ms	5152 KB	Output is correct
15	Correct	150 ms	5216 KB	Output is correct
16	Correct	161 ms	5216 KB	Output is correct
17	Correct	153 ms	5248 KB	Output is correct
18	Correct	1469 ms	17632 KB	Output is correct
19	Correct	1450 ms	17096 KB	Output is correct
20	Correct	1504 ms	17096 KB	Output is correct
21	Correct	150 ms	5216 KB	Output is correct
22	Correct	144 ms	5216 KB	Output is correct
23	Correct	481 ms	11220 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	150 ms	5216 KB	Output is correct
3	Correct	148 ms	5344 KB	Output is correct
4	Correct	1526 ms	17224 KB	Output is correct
5	Correct	150 ms	5216 KB	Output is correct
6	Correct	149 ms	5236 KB	Output is correct
7	Correct	149 ms	5216 KB	Output is correct
8	Correct	150 ms	5216 KB	Output is correct
9	Correct	149 ms	5216 KB	Output is correct
10	Correct	150 ms	5216 KB	Output is correct
11	Correct	149 ms	5216 KB	Output is correct
12	Correct	145 ms	5216 KB	Output is correct
13	Correct	150 ms	5216 KB	Output is correct
14	Correct	1493 ms	17116 KB	Output is correct
15	Correct	149 ms	5112 KB	Output is correct
16	Correct	1438 ms	17224 KB	Output is correct
17	Correct	1448 ms	17096 KB	Output is correct
18	Correct	1 ms	364 KB	Output is correct

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	15 ms	876 KB	Output is correct
3	Correct	15 ms	876 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	364 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	364 KB	Output is correct
16	Correct	15 ms	876 KB	Output is correct
17	Correct	150 ms	2912 KB	Output is correct
18	Correct	1 ms	364 KB	Output is correct
19	Correct	1 ms	364 KB	Output is correct
20	Incorrect	1 ms	364 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Submission #335109

Compilation message