답안 #266443

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
266443 2020-08-15T09:39:48 Z define 이상한 기계 (APIO19_strange_device) C++17
100 / 100
3573 ms 65348 KB
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define len(s) (int)s.size()
 
template<class T> inline bool chmin(T &a, T b){
	if(a>b){a=b;return true;}
	return false;
}
template<class T> inline bool chmax(T &a, T b){
	if(a<b){a=b;return true;}
	return false;
}
constexpr int mod = 1e9+7;
constexpr long long inf = 3e18;

int gcd(int x,int y){
	return (y?gcd(y,x%y):x);
}
int A,B,N;
void solve1(){
	int ans=0;
	while(N--){
		int a,b;cin>>a>>b;
		ans+=b-a+1;
	}
	cout<<ans<<endl;
	exit(0);
}
signed main(){
	cin>>N>>A>>B;
	int x=(B%A+1)%A;
	int g=gcd(A,x);
	if(inf/(A/g)<B)solve1();
	int lc=A/g*B;
	set<P>st;
	rep(i,N){
		int a,b;cin>>a>>b;
		if(b-a+1>=lc){
			cout<<lc<<endl;return 0;
		}
		if(a/lc!=b/lc){
			st.insert({a%lc,lc-1});
			st.insert({0,b%lc});
		}else {
			st.insert({a%lc,b%lc});
		}
	}
	int ans=0,now=-1;
	for(P i:st){
		if(i.first<=now){
			ans+=max(0ll,i.second-now);
			chmax(now,i.second);
		}else {
			ans+=i.second-i.first+1;
			now=i.second;
		}
	}
	cout<<ans<<endl;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 32 ms 1016 KB Output is correct
3 Correct 36 ms 896 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 288 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 1 ms 256 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Correct 35 ms 1408 KB Output is correct
17 Correct 327 ms 8048 KB Output is correct
18 Correct 1 ms 360 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 2149 ms 416 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 3270 ms 62952 KB Output is correct
3 Correct 3272 ms 62972 KB Output is correct
4 Correct 3408 ms 65148 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 3270 ms 62952 KB Output is correct
3 Correct 3272 ms 62972 KB Output is correct
4 Correct 3408 ms 65148 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 3573 ms 65192 KB Output is correct
7 Correct 3276 ms 65012 KB Output is correct
8 Correct 3349 ms 65028 KB Output is correct
9 Correct 3549 ms 65348 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 3270 ms 62952 KB Output is correct
3 Correct 3272 ms 62972 KB Output is correct
4 Correct 3408 ms 65148 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 319 ms 7928 KB Output is correct
7 Correct 321 ms 7904 KB Output is correct
8 Correct 323 ms 7928 KB Output is correct
9 Correct 326 ms 7956 KB Output is correct
10 Correct 324 ms 7928 KB Output is correct
11 Correct 319 ms 7972 KB Output is correct
12 Correct 325 ms 7928 KB Output is correct
13 Correct 345 ms 8056 KB Output is correct
14 Correct 317 ms 8056 KB Output is correct
15 Correct 326 ms 7928 KB Output is correct
16 Correct 334 ms 7544 KB Output is correct
17 Correct 322 ms 7544 KB Output is correct
18 Correct 3264 ms 64428 KB Output is correct
19 Correct 3367 ms 64504 KB Output is correct
20 Correct 3295 ms 64688 KB Output is correct
21 Correct 323 ms 7288 KB Output is correct
22 Correct 323 ms 7288 KB Output is correct
23 Correct 999 ms 1784 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 332 ms 6676 KB Output is correct
3 Correct 321 ms 6776 KB Output is correct
4 Correct 3250 ms 62968 KB Output is correct
5 Correct 324 ms 6520 KB Output is correct
6 Correct 332 ms 6564 KB Output is correct
7 Correct 326 ms 6520 KB Output is correct
8 Correct 334 ms 6776 KB Output is correct
9 Correct 322 ms 6652 KB Output is correct
10 Correct 328 ms 6648 KB Output is correct
11 Correct 323 ms 6520 KB Output is correct
12 Correct 336 ms 6648 KB Output is correct
13 Correct 323 ms 6520 KB Output is correct
14 Correct 3314 ms 62968 KB Output is correct
15 Correct 326 ms 6520 KB Output is correct
16 Correct 3261 ms 63128 KB Output is correct
17 Correct 3347 ms 64468 KB Output is correct
18 Correct 1 ms 256 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 32 ms 1016 KB Output is correct
3 Correct 36 ms 896 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 288 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 1 ms 256 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Correct 35 ms 1408 KB Output is correct
17 Correct 327 ms 8048 KB Output is correct
18 Correct 1 ms 360 KB Output is correct
19 Correct 1 ms 256 KB Output is correct
20 Correct 1 ms 256 KB Output is correct
21 Correct 1 ms 256 KB Output is correct
22 Correct 1 ms 256 KB Output is correct
23 Correct 1 ms 256 KB Output is correct
24 Correct 0 ms 256 KB Output is correct
25 Correct 4 ms 384 KB Output is correct
26 Correct 4 ms 384 KB Output is correct
27 Correct 4 ms 384 KB Output is correct
28 Correct 2149 ms 416 KB Output is correct
29 Correct 1 ms 324 KB Output is correct
30 Correct 3270 ms 62952 KB Output is correct
31 Correct 3272 ms 62972 KB Output is correct
32 Correct 3408 ms 65148 KB Output is correct
33 Correct 1 ms 256 KB Output is correct
34 Correct 3573 ms 65192 KB Output is correct
35 Correct 3276 ms 65012 KB Output is correct
36 Correct 3349 ms 65028 KB Output is correct
37 Correct 3549 ms 65348 KB Output is correct
38 Correct 1 ms 256 KB Output is correct
39 Correct 319 ms 7928 KB Output is correct
40 Correct 321 ms 7904 KB Output is correct
41 Correct 323 ms 7928 KB Output is correct
42 Correct 326 ms 7956 KB Output is correct
43 Correct 324 ms 7928 KB Output is correct
44 Correct 319 ms 7972 KB Output is correct
45 Correct 325 ms 7928 KB Output is correct
46 Correct 345 ms 8056 KB Output is correct
47 Correct 317 ms 8056 KB Output is correct
48 Correct 326 ms 7928 KB Output is correct
49 Correct 334 ms 7544 KB Output is correct
50 Correct 322 ms 7544 KB Output is correct
51 Correct 3264 ms 64428 KB Output is correct
52 Correct 3367 ms 64504 KB Output is correct
53 Correct 3295 ms 64688 KB Output is correct
54 Correct 323 ms 7288 KB Output is correct
55 Correct 323 ms 7288 KB Output is correct
56 Correct 999 ms 1784 KB Output is correct
57 Correct 1 ms 256 KB Output is correct
58 Correct 332 ms 6676 KB Output is correct
59 Correct 321 ms 6776 KB Output is correct
60 Correct 3250 ms 62968 KB Output is correct
61 Correct 324 ms 6520 KB Output is correct
62 Correct 332 ms 6564 KB Output is correct
63 Correct 326 ms 6520 KB Output is correct
64 Correct 334 ms 6776 KB Output is correct
65 Correct 322 ms 6652 KB Output is correct
66 Correct 328 ms 6648 KB Output is correct
67 Correct 323 ms 6520 KB Output is correct
68 Correct 336 ms 6648 KB Output is correct
69 Correct 323 ms 6520 KB Output is correct
70 Correct 3314 ms 62968 KB Output is correct
71 Correct 326 ms 6520 KB Output is correct
72 Correct 3261 ms 63128 KB Output is correct
73 Correct 3347 ms 64468 KB Output is correct
74 Correct 1 ms 256 KB Output is correct
75 Correct 1 ms 256 KB Output is correct
76 Correct 1 ms 256 KB Output is correct
77 Correct 1 ms 256 KB Output is correct
78 Correct 1 ms 256 KB Output is correct
79 Correct 41 ms 1272 KB Output is correct
80 Correct 3360 ms 64348 KB Output is correct
81 Correct 3367 ms 64532 KB Output is correct
82 Correct 3396 ms 64372 KB Output is correct
83 Correct 3289 ms 64400 KB Output is correct
84 Correct 3425 ms 64516 KB Output is correct
85 Correct 3429 ms 64356 KB Output is correct
86 Correct 1034 ms 1784 KB Output is correct
87 Correct 1 ms 384 KB Output is correct