oj.uz

Submission #139794

# Submission time Handle Problem Language Result Execution time Memory
139794 2019-08-01T12:22:30 Z FedericoS Strange Device (APIO19_strange_device) C++14
5 / 100
 2953 ms 81316 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef long double ld;

ll INF=1e18+1;
ll N,A,B,M;
ll L[1000006],R[1000006];
ll x,y;
vector<pll> S;
vector<pll> V;
ll ans,K;

int main(){
	cin>>N>>A>>B;

	if((ld)A*(ld)B>(ld)INF)
		M=INF;
	else
		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 348 KB Output is correct
2 Correct 29 ms 1544 KB Output is correct
3 Correct 30 ms 1648 KB Output is correct
4 Incorrect 2 ms 256 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 256 KB Output is correct
2 Incorrect 2 ms 380 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 376 KB Output is correct
2 Correct 5 ms 508 KB Output is correct
3 Correct 5 ms 536 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 1980 ms 48924 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 2875 ms 81316 KB Output is correct
3 Incorrect 2768 ms 80292 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 2875 ms 81316 KB Output is correct
3 Incorrect 2768 ms 80292 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 2875 ms 81316 KB Output is correct
3 Incorrect 2768 ms 80292 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 256 KB Output is correct
2 Correct 292 ms 11616 KB Output is correct
3 Correct 294 ms 10360 KB Output is correct
4 Correct 2953 ms 80388 KB Output is correct
5 Correct 291 ms 10204 KB Output is correct
6 Correct 292 ms 10216 KB Output is correct
7 Correct 289 ms 10192 KB Output is correct
8 Correct 288 ms 10216 KB Output is correct
9 Correct 292 ms 10152 KB Output is correct
10 Correct 287 ms 10204 KB Output is correct
11 Correct 289 ms 10264 KB Output is correct
12 Correct 283 ms 10276 KB Output is correct
13 Correct 291 ms 9892 KB Output is correct
14 Correct 2936 ms 80292 KB Output is correct
15 Incorrect 319 ms 9984 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 348 KB Output is correct
2 Correct 29 ms 1544 KB Output is correct
3 Correct 30 ms 1648 KB Output is correct
4 Incorrect 2 ms 256 KB Output isn't correct
5 Halted 0 ms 0 KB -