oj.uz

Submission #265760

# Submission time Handle Problem Language Result Execution time Memory
265760 2020-08-15T04:40:40 Z kaage Strange Device (APIO19_strange_device) C++17
15 / 100
 658 ms 64044 KB 
#line 2 "/Users/kaage/Desktop/ProgrammingWorkspace/library/other/template.hpp"
#define _CRT_SECURE_NO_WARNINGS
#pragma target("avx2")
#pragma optimize("O3")
#pragma optimize("unroll-loops")
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define all(V) V.begin(),V.end()
typedef long long lint;
typedef unsigned long long ulint;
typedef std::pair<int, int> P;
typedef std::pair<lint, lint> LP;
constexpr int INF = INT_MAX/2;
constexpr lint LINF = LLONG_MAX/2;
constexpr double eps = DBL_EPSILON;
constexpr double PI=3.141592653589793238462643383279;
template<class T>
class prique :public std::priority_queue<T, std::vector<T>, std::greater<T>> {};
template <class T, class U>
inline bool chmax(T& lhs, const U& rhs) {
	if (lhs < rhs) {
		lhs = rhs;
		return 1;
	}
	return 0;
}
template <class T, class U>
inline bool chmin(T& lhs, const U& rhs) {
	if (lhs > rhs) {
		lhs = rhs;
		return 1;
	}
	return 0;
}
inline lint gcd(lint a, lint b) {
	while (b) {
		lint c = a;
		a = b; b = c % b;
	}
	return a;
}
inline lint lcm(lint a, lint b) {
	return a / gcd(a, b) * b;
}
bool isprime(lint n) {
	if (n == 1)return false;
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0)return false;
	}
	return true;
}
template<typename T>
T mypow(T a, lint b) {
	T res(1);
	while(b){
		if(b&1)res*=a;
		a*=a;
		b>>=1;
	}
	return res;
}
lint modpow(lint a, lint b, lint m) {
	lint res(1);
	while(b){
		if(b&1){
			res*=a;res%=m;
		}
		a*=a;a%=m;
		b>>=1;
	}
	return res;
}
template<typename T>
void printArray(std::vector<T>& vec) {
	rep(i, vec.size()){
		std::cout << vec[i];
		std::cout<<(i==(int)vec.size()-1?"\n":" ");
	}
}
template<typename T>
void printArray(T l, T r) {
	T rprev = std::prev(r);
	for (T i = l; i != rprev; i++) {
		std::cout << *i << " ";
	}
	std::cout << *rprev << std::endl;
}
LP extGcd(lint a,lint b) {
	if(b==0)return {1,0};
	LP s=extGcd(b,a%b);
	std::swap(s.first,s.second);
	s.second-=a/b*s.first;
	return s;
}
LP ChineseRem(const lint& b1,const lint& m1,const lint& b2,const lint& m2) {
	lint p=extGcd(m1,m2).first;
	lint tmp=(b2-b1)*p%m2;
	lint r=(b1+m1*tmp+m1*m2)%(m1*m2);
	return std::make_pair(r,m1*m2);
}
/*template<typename F>
inline constexpr decltype(auto) lambda_fix(F&& f){
	return [f=std::forward<F>(f)](auto&&... args){
		return f(f,std::forward<decltype(args)>(args)...);
	};
}*/
#line 2 "main.cpp"
int n;
lint a,b,l[1000010],r[1000010];
int main(){
	scanf("%d%lld%lld",&n,&a,&b);
	rep(i,n)scanf("%lld%lld",l+i,r+i);
	lint tmp=a/gcd(b+1,a);
	if(1000000000000000001/b<=tmp){
		lint ans=0;
		rep(i,n)ans+=r[i]-l[i]+1;
		printf("%lld\n",ans);
		return 0;
	}
	lint per=tmp*b;
	std::vector<LP> vec;
	rep(i,n){
		if(r[i]-l[i]+1>=per){
			printf("%lld\n",per);
			return 0;
		}
		if(l[i]/per!=r[i]/per){
			vec.emplace_back(l[i]%per,per);
			vec.emplace_back(0,(r[i]+1)%per);
		}
		else vec.emplace_back(l[i]%per,r[i]%per+1);
	}
	std::sort(all(vec));
	lint nowlast=-1,ans=0;
	for(const LP& p:vec){
		if(nowlast<p.first){
			ans+=p.second-p.first;
			nowlast=p.second;
		}
		else{
			ans+=p.second-nowlast;
			nowlast=p.second;
		}
	}
	printf("%lld\n",ans);
}

Compilation message

/Users/kaage/Desktop/ProgrammingWorkspace/library/other/template.hpp:3: warning: ignoring #pragma target  [-Wunknown-pragmas]
/Users/kaage/Desktop/ProgrammingWorkspace/library/other/template.hpp:4: warning: ignoring #pragma optimize  [-Wunknown-pragmas]
/Users/kaage/Desktop/ProgrammingWorkspace/library/other/template.hpp:5: warning: ignoring #pragma optimize  [-Wunknown-pragmas]
main.cpp: In function 'int main()':
main.cpp:5:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
main.cpp:6:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 6 ms 1280 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

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

Subtask #3
0 / 5.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 646 ms 34660 KB Output is correct
3 Correct 649 ms 57716 KB Output is correct
4 Correct 617 ms 63840 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 646 ms 34660 KB Output is correct
3 Correct 649 ms 57716 KB Output is correct
4 Correct 617 ms 63840 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 636 ms 63904 KB Output is correct
7 Correct 591 ms 63692 KB Output is correct
8 Correct 603 ms 63580 KB Output is correct
9 Correct 656 ms 64044 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 646 ms 34660 KB Output is correct
3 Correct 649 ms 57716 KB Output is correct
4 Correct 617 ms 63840 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 58 ms 7788 KB Output is correct
7 Correct 60 ms 7788 KB Output is correct
8 Correct 56 ms 7788 KB Output is correct
9 Correct 58 ms 7788 KB Output is correct
10 Correct 68 ms 7788 KB Output is correct
11 Correct 58 ms 7788 KB Output is correct
12 Correct 54 ms 7788 KB Output is correct
13 Correct 64 ms 7788 KB Output is correct
14 Correct 58 ms 7788 KB Output is correct
15 Incorrect 59 ms 7788 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 82 ms 7788 KB Output is correct
3 Correct 58 ms 7788 KB Output is correct
4 Correct 658 ms 41692 KB Output is correct
5 Correct 58 ms 7788 KB Output is correct
6 Correct 60 ms 7752 KB Output is correct
7 Correct 65 ms 7916 KB Output is correct
8 Correct 59 ms 7760 KB Output is correct
9 Correct 56 ms 7768 KB Output is correct
10 Correct 61 ms 7820 KB Output is correct
11 Correct 62 ms 7788 KB Output is correct
12 Correct 63 ms 7788 KB Output is correct
13 Correct 69 ms 7788 KB Output is correct
14 Incorrect 639 ms 41696 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 6 ms 1280 KB Output isn't correct
3 Halted 0 ms 0 KB -