Submission #233399

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
233399	2020-05-20T12:09:35 Z	priyansh5525	Strange Device (APIO19_strange_device)	C++17	35 / 100	633 ms	77936 KB

strange_device

#include<bits/stdc++.h>
	using namespace std;
	#define ll long long int
	#define pii pair<long long int,long long int>
	#define vi vector<long long int >
	#define vvi vector<vector< long long int>>
	#define MP make_pair
	#define PB push_back 
	#define pb pop_back
	#define PF push_front
	#define pf pop_front
	#define MOD 1000000007

	int main()
	{
		ios_base::sync_with_stdio(false);
		cin.tie(NULL);
		ll n,a,b;
		vector<pii> vec;
		cin>>n>>a>>b;
		for(ll i=0;i<n;i++)
		{
			ll x,y;
			cin>>x>>y;
			vec.PB(MP(x,y));
		}
		// solve equation t2 = x*fac+t1
		ll fac = a/__gcd(a,b+1);
		fac*=b;

		ll ans=0;
		vector<pii> ve;
		for(ll i=0;i<n;i++)
		{
			ll x=vec[i].first,y=vec[i].second;
			if(y-x+1>=fac)
			{
				ans=fac;
				break;
			}
			if((x%fac)<=(y%fac))
			{
				ve.PB(MP(x%fac,y%fac));
			}
			else
			{
				ve.PB(MP(x%fac,fac-1));
				ve.PB(MP(0,y%fac));
			}
		}
		if(ans==0)
		{
		sort(ve.begin(),ve.end());
		ll k=ve.size();
		for(ll i=0;i<k;i++)
		{
			ll x=ve[i].first,y=ve[i].second;
			ll j=i+1;
			//cout<<x<<" "<<y<<endl;
			while(j<k && ve[j].first<=(y+1))
			{
				y=max(ve[j].second,y);
				//cout<<x<<" "<<y<<endl;
				j++;
			}
			ans+= (y-x+1);
			i=j-1;
		}
	 	}
	 	cout<<ans<<"\n";
		return 0;
	}

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	10 ms	1280 KB	Output is correct
3	Correct	10 ms	1280 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	5 ms	384 KB	Output is correct
11	Correct	4 ms	384 KB	Output is correct
12	Correct	5 ms	256 KB	Output is correct
13	Correct	4 ms	384 KB	Output is correct
14	Correct	5 ms	384 KB	Output is correct
15	Correct	5 ms	384 KB	Output is correct
16	Correct	10 ms	1280 KB	Output is correct
17	Correct	65 ms	8684 KB	Output is correct
18	Incorrect	4 ms	384 KB	Output isn't correct

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	4 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Incorrect	5 ms	384 KB	Output isn't correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	5 ms	512 KB	Output is correct
5	Correct	401 ms	42688 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	528 ms	44780 KB	Output is correct
3	Correct	518 ms	60608 KB	Output is correct
4	Correct	531 ms	58436 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	528 ms	44780 KB	Output is correct
3	Correct	518 ms	60608 KB	Output is correct
4	Correct	531 ms	58436 KB	Output is correct
5	Correct	4 ms	384 KB	Output is correct
6	Correct	548 ms	58384 KB	Output is correct
7	Correct	530 ms	58436 KB	Output is correct
8	Correct	539 ms	58432 KB	Output is correct
9	Correct	581 ms	58432 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	528 ms	44780 KB	Output is correct
3	Correct	518 ms	60608 KB	Output is correct
4	Correct	531 ms	58436 KB	Output is correct
5	Correct	4 ms	384 KB	Output is correct
6	Correct	56 ms	8684 KB	Output is correct
7	Correct	63 ms	8684 KB	Output is correct
8	Correct	61 ms	8728 KB	Output is correct
9	Correct	59 ms	8688 KB	Output is correct
10	Correct	59 ms	8684 KB	Output is correct
11	Correct	60 ms	8680 KB	Output is correct
12	Correct	55 ms	8728 KB	Output is correct
13	Correct	62 ms	8680 KB	Output is correct
14	Correct	57 ms	8684 KB	Output is correct
15	Correct	66 ms	8684 KB	Output is correct
16	Correct	61 ms	8684 KB	Output is correct
17	Correct	59 ms	8680 KB	Output is correct
18	Correct	543 ms	58484 KB	Output is correct
19	Correct	533 ms	58688 KB	Output is correct
20	Correct	581 ms	58552 KB	Output is correct
21	Correct	62 ms	8684 KB	Output is correct
22	Correct	56 ms	8660 KB	Output is correct
23	Correct	177 ms	30536 KB	Output is correct

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	61 ms	8684 KB	Output is correct
3	Correct	60 ms	8684 KB	Output is correct
4	Correct	633 ms	77908 KB	Output is correct
5	Correct	60 ms	8680 KB	Output is correct
6	Correct	63 ms	8684 KB	Output is correct
7	Correct	60 ms	8680 KB	Output is correct
8	Correct	60 ms	8676 KB	Output is correct
9	Correct	65 ms	8684 KB	Output is correct
10	Correct	60 ms	8684 KB	Output is correct
11	Correct	63 ms	8680 KB	Output is correct
12	Correct	55 ms	8684 KB	Output is correct
13	Correct	60 ms	8680 KB	Output is correct
14	Correct	623 ms	77936 KB	Output is correct
15	Correct	63 ms	8684 KB	Output is correct
16	Correct	533 ms	48956 KB	Output is correct
17	Correct	546 ms	57280 KB	Output is correct
18	Incorrect	4 ms	384 KB	Output isn't correct

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	10 ms	1280 KB	Output is correct
3	Correct	10 ms	1280 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	5 ms	384 KB	Output is correct
11	Correct	4 ms	384 KB	Output is correct
12	Correct	5 ms	256 KB	Output is correct
13	Correct	4 ms	384 KB	Output is correct
14	Correct	5 ms	384 KB	Output is correct
15	Correct	5 ms	384 KB	Output is correct
16	Correct	10 ms	1280 KB	Output is correct
17	Correct	65 ms	8684 KB	Output is correct
18	Incorrect	4 ms	384 KB	Output isn't correct

Submission #233399

Compilation message