oj.uz

Submission #139792

# Submission time Handle Problem Language Result Execution time Memory
139792 2019-08-01T12:19:57 Z FedericoS Strange Device (APIO19_strange_device) C++14
5 / 100
 2940 ms 80136 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pll;

ll N,A,B;
ll L[1000006],R[1000006];
ll x,y;
vector<pll> S;
vector<pll> V;
ll ans,K;

int main(){
	cin>>N>>A>>B;
	ll M=(A*B);
	for(int i=0;i<N;i++){

		cin>>L[i]>>R[i];
		x=L[i]%M;
		y=R[i]%M;

		if(y<x){
			if(R[i]-L[i]>=M){
				V.push_back({0,1});
				V.push_back({M,-1});
			}
			else{
				V.push_back({0,1});
				V.push_back({y+1,-1});
				V.push_back({x,1});
				V.push_back({M,-1});
			}
		}
		else{
			V.push_back({x,1});
			V.push_back({y+1,-1});
		}
	}

	V.push_back({0,0});
	sort(V.begin(),V.end());


	for(pll p:V){
		if(!S.empty() and p.first==S.back().first)
			S.back().second+=p.second;
		else
			S.push_back(p);
	}

	pll q=*S.begin();
	for(pll p:S){
		if(K) 
			ans+=p.first-q.first;
		K+=p.second;
		q=p;
	}

	cout<<ans;

}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 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 2 ms 256 KB Output is correct
2 Correct 5 ms 604 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 1980 ms 48340 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2867 ms 79736 KB Output is correct
3 Incorrect 2766 ms 79496 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2867 ms 79736 KB Output is correct
3 Incorrect 2766 ms 79496 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2867 ms 79736 KB Output is correct
3 Incorrect 2766 ms 79496 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 294 ms 9688 KB Output is correct
3 Correct 297 ms 9172 KB Output is correct
4 Correct 2940 ms 79492 KB Output is correct
5 Correct 300 ms 8680 KB Output is correct
6 Correct 293 ms 8608 KB Output is correct
7 Correct 291 ms 8776 KB Output is correct
8 Correct 286 ms 8872 KB Output is correct
9 Correct 295 ms 8932 KB Output is correct
10 Correct 288 ms 8960 KB Output is correct
11 Correct 293 ms 8900 KB Output is correct
12 Correct 285 ms 9340 KB Output is correct
13 Correct 295 ms 9508 KB Output is correct
14 Correct 2928 ms 80136 KB Output is correct
15 Incorrect 288 ms 8924 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

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