oj.uz

Submission #139797

# Submission time Handle Problem Language Result Execution time Memory
139797 2019-08-01T12:24:05 Z FedericoS Strange Device (APIO19_strange_device) C++14
5 / 100
 3031 ms 79876 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});
	V.push_back({M,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 376 KB Output is correct
2 Correct 30 ms 1396 KB Output is correct
3 Correct 31 ms 1392 KB Output is correct
4 Incorrect 2 ms 420 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 252 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 364 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 1969 ms 47864 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 2830 ms 79448 KB Output is correct
3 Incorrect 2895 ms 79368 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 2830 ms 79448 KB Output is correct
3 Incorrect 2895 ms 79368 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 2830 ms 79448 KB Output is correct
3 Incorrect 2895 ms 79368 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 252 KB Output is correct
2 Correct 288 ms 8916 KB Output is correct
3 Correct 290 ms 9068 KB Output is correct
4 Correct 3031 ms 79500 KB Output is correct
5 Correct 291 ms 8908 KB Output is correct
6 Correct 291 ms 9172 KB Output is correct
7 Correct 314 ms 8944 KB Output is correct
8 Correct 292 ms 8876 KB Output is correct
9 Correct 288 ms 8916 KB Output is correct
10 Correct 296 ms 8964 KB Output is correct
11 Correct 293 ms 8948 KB Output is correct
12 Correct 315 ms 9456 KB Output is correct
13 Correct 292 ms 9364 KB Output is correct
14 Correct 2925 ms 79876 KB Output is correct
15 Incorrect 296 ms 9120 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 376 KB Output is correct
2 Correct 30 ms 1396 KB Output is correct
3 Correct 31 ms 1392 KB Output is correct
4 Incorrect 2 ms 420 KB Output isn't correct
5 Halted 0 ms 0 KB -