Submission #674722

#	Time	Username	Problem	Language	Result	Execution time	Memory
674722		vjudge1	Strange Device (APIO19_strange_device)	C++17	100 / 100	642 ms	100132 KiB

strange_device

#include<bits/stdc++.h>
template<class T> inline void read(T &x){
	x=0; register char c=getchar(); register bool f=0;
	while(!isdigit(c))f^=c=='-',c=getchar();
	while(isdigit(c))x=x*10+c-'0',c=getchar(); if(f)x=-x;
}
template<class T> inline T gcd(T n,T m){return m?gcd(m,n%m):n;}
const int N=1e6+10;
int n;
long long A,B,l,r,ans;
std::map<long long,int> sum;
int main(){
#ifdef memset0
	freopen("1.in","r",stdin);
#endif
	read(n),read(A),read(B);
	A/=gcd(A,B+1);
	if(A>(long long)(2e18)/B){
		for(int i=1;i<=n;i++){
			read(l),read(r);
			ans+=r-l+1;
		}
		printf("%lld\n",ans);
		return 0;
	}
	// printf("%lld %lld\n",A,B);
	for(int i=1;i<=n;i++){
		read(l),read(r);
		if(r-l+1>=A*B){
			printf("%lld\n",A*B);
			return 0;
		}
		l%=A*B,r%=A*B;
		// printf("> %lld %lld\n",l,r);
		if(l<=r){
			sum[l]++,sum[r+1]--;
		}else{
			sum[0]++,sum[r+1]--;
			sum[l]++,sum[A*B]--;
		}
	}
	sum[A*B]+=0;
	long long cnt=0,lst=0;
	for(const auto &it:sum){
		if(cnt)ans+=it.first-lst;
		cnt+=it.second;
		lst=it.first;
	}
	printf("%lld\n",ans);
}

Compilation message (stderr)

strange_device.cpp: In function 'void read(T&)':
strange_device.cpp:3:21: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
    3 |  x=0; register char c=getchar(); register bool f=0;
      |                     ^
strange_device.cpp:3:48: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
    3 |  x=0; register char c=getchar(); register bool f=0;
      |                                                ^
strange_device.cpp:5:2: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
    5 |  while(isdigit(c))x=x*10+c-'0',c=getchar(); if(f)x=-x;
      |  ^~~~~
strange_device.cpp:5:45: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
    5 |  while(isdigit(c))x=x*10+c-'0',c=getchar(); if(f)x=-x;
      |                                             ^~
strange_device.cpp: In instantiation of 'void read(T&) [with T = int]':
strange_device.cpp:16:8:   required from here
strange_device.cpp:3:21: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
    3 |  x=0; register char c=getchar(); register bool f=0;
      |                     ^
strange_device.cpp:3:48: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
    3 |  x=0; register char c=getchar(); register bool f=0;
      |                                                ^
strange_device.cpp: In instantiation of 'void read(T&) [with T = long long int]':
strange_device.cpp:16:16:   required from here
strange_device.cpp:3:21: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
    3 |  x=0; register char c=getchar(); register bool f=0;
      |                     ^
strange_device.cpp:3:48: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
    3 |  x=0; register char c=getchar(); register bool f=0;
      |                                                ^

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20
• Subtask 8: 30 / 30