답안 #933754

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
933754	2024-02-26T09:04:24 Z	irmuun	이상한 기계 (APIO19_strange_device)	C++17	100 / 100	418 ms	71472 KB

strange_device

#include<bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,a,b;
    cin>>n>>a>>b;
    ll l[n+5],r[n+5];
    ll g=a/gcd((b+1)%a,a),MX=1e18+1;
    if(MX/b>=g){
        g=g*b;
    }
    else{
        g=MX;
    }
    for(ll i=1;i<=n;i++){
        cin>>l[i]>>r[i];
    }
    vector<pair<ll,ll>>v;
    for(ll i=1;i<=n;i++){
        if(r[i]-l[i]+1>=g){
            cout<<g;
            return 0;
        }
        ll L=l[i]%g,R=r[i]%g;
        if(L<=R){
            v.pb({L,R});
        }
        else{
            v.pb({0,R});
            v.pb({L,g-1});
        }
    }
    sort(all(v));
    ll ans=0;
    for(ll i=0;i<v.size();){
        ll nxt=i,curR=v[i].ss;
        while(nxt+1<v.size()&&v[nxt+1].ff<=curR){
            nxt++;
            curR=max(curR,v[nxt].ss);
        }
        ans+=curR-v[i].ff+1;
        i=nxt+1;
    }
    cout<<ans;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:44:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(ll i=0;i<v.size();){
      |                ~^~~~~~~~~
strange_device.cpp:46:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         while(nxt+1<v.size()&&v[nxt+1].ff<=curR){
      |               ~~~~~^~~~~~~~~

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	3 ms	860 KB	Output is correct
3	Correct	5 ms	860 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	344 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	3 ms	860 KB	Output is correct
17	Correct	38 ms	4044 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	메모리	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct

Subtask #3
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	600 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	217 ms	34268 KB	Output is correct

Subtask #4
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	314 ms	34392 KB	Output is correct
3	Correct	305 ms	69928 KB	Output is correct
4	Correct	307 ms	71340 KB	Output is correct

Subtask #5
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	314 ms	34392 KB	Output is correct
3	Correct	305 ms	69928 KB	Output is correct
4	Correct	307 ms	71340 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	308 ms	71224 KB	Output is correct
7	Correct	329 ms	70832 KB	Output is correct
8	Correct	322 ms	71348 KB	Output is correct
9	Correct	360 ms	69944 KB	Output is correct

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	314 ms	34392 KB	Output is correct
3	Correct	305 ms	69928 KB	Output is correct
4	Correct	307 ms	71340 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	35 ms	7876 KB	Output is correct
7	Correct	35 ms	7864 KB	Output is correct
8	Correct	31 ms	7884 KB	Output is correct
9	Correct	36 ms	7748 KB	Output is correct
10	Correct	33 ms	7884 KB	Output is correct
11	Correct	34 ms	7896 KB	Output is correct
12	Correct	31 ms	7744 KB	Output is correct
13	Correct	36 ms	7884 KB	Output is correct
14	Correct	32 ms	7888 KB	Output is correct
15	Correct	37 ms	7752 KB	Output is correct
16	Correct	39 ms	7732 KB	Output is correct
17	Correct	34 ms	7884 KB	Output is correct
18	Correct	343 ms	69932 KB	Output is correct
19	Correct	322 ms	70968 KB	Output is correct
20	Correct	357 ms	70452 KB	Output is correct
21	Correct	38 ms	7708 KB	Output is correct
22	Correct	30 ms	7888 KB	Output is correct
23	Correct	93 ms	28520 KB	Output is correct

Subtask #7
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	33 ms	4056 KB	Output is correct
3	Correct	34 ms	7896 KB	Output is correct
4	Correct	391 ms	70452 KB	Output is correct
5	Correct	34 ms	7896 KB	Output is correct
6	Correct	37 ms	7748 KB	Output is correct
7	Correct	39 ms	8004 KB	Output is correct
8	Correct	35 ms	7888 KB	Output is correct
9	Correct	33 ms	7884 KB	Output is correct
10	Correct	34 ms	7752 KB	Output is correct
11	Correct	38 ms	7748 KB	Output is correct
12	Correct	29 ms	7928 KB	Output is correct
13	Correct	38 ms	7896 KB	Output is correct
14	Correct	353 ms	70208 KB	Output is correct
15	Correct	38 ms	7884 KB	Output is correct
16	Correct	418 ms	71352 KB	Output is correct
17	Correct	307 ms	70836 KB	Output is correct
18	Correct	1 ms	348 KB	Output is correct

Subtask #8
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	3 ms	860 KB	Output is correct
3	Correct	5 ms	860 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	344 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	3 ms	860 KB	Output is correct
17	Correct	38 ms	4044 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	344 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	0 ms	348 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	1 ms	348 KB	Output is correct
26	Correct	1 ms	600 KB	Output is correct
27	Correct	1 ms	348 KB	Output is correct
28	Correct	217 ms	34268 KB	Output is correct
29	Correct	0 ms	348 KB	Output is correct
30	Correct	314 ms	34392 KB	Output is correct
31	Correct	305 ms	69928 KB	Output is correct
32	Correct	307 ms	71340 KB	Output is correct
33	Correct	0 ms	344 KB	Output is correct
34	Correct	308 ms	71224 KB	Output is correct
35	Correct	329 ms	70832 KB	Output is correct
36	Correct	322 ms	71348 KB	Output is correct
37	Correct	360 ms	69944 KB	Output is correct
38	Correct	1 ms	344 KB	Output is correct
39	Correct	35 ms	7876 KB	Output is correct
40	Correct	35 ms	7864 KB	Output is correct
41	Correct	31 ms	7884 KB	Output is correct
42	Correct	36 ms	7748 KB	Output is correct
43	Correct	33 ms	7884 KB	Output is correct
44	Correct	34 ms	7896 KB	Output is correct
45	Correct	31 ms	7744 KB	Output is correct
46	Correct	36 ms	7884 KB	Output is correct
47	Correct	32 ms	7888 KB	Output is correct
48	Correct	37 ms	7752 KB	Output is correct
49	Correct	39 ms	7732 KB	Output is correct
50	Correct	34 ms	7884 KB	Output is correct
51	Correct	343 ms	69932 KB	Output is correct
52	Correct	322 ms	70968 KB	Output is correct
53	Correct	357 ms	70452 KB	Output is correct
54	Correct	38 ms	7708 KB	Output is correct
55	Correct	30 ms	7888 KB	Output is correct
56	Correct	93 ms	28520 KB	Output is correct
57	Correct	0 ms	344 KB	Output is correct
58	Correct	33 ms	4056 KB	Output is correct
59	Correct	34 ms	7896 KB	Output is correct
60	Correct	391 ms	70452 KB	Output is correct
61	Correct	34 ms	7896 KB	Output is correct
62	Correct	37 ms	7748 KB	Output is correct
63	Correct	39 ms	8004 KB	Output is correct
64	Correct	35 ms	7888 KB	Output is correct
65	Correct	33 ms	7884 KB	Output is correct
66	Correct	34 ms	7752 KB	Output is correct
67	Correct	38 ms	7748 KB	Output is correct
68	Correct	29 ms	7928 KB	Output is correct
69	Correct	38 ms	7896 KB	Output is correct
70	Correct	353 ms	70208 KB	Output is correct
71	Correct	38 ms	7884 KB	Output is correct
72	Correct	418 ms	71352 KB	Output is correct
73	Correct	307 ms	70836 KB	Output is correct
74	Correct	1 ms	348 KB	Output is correct
75	Correct	0 ms	348 KB	Output is correct
76	Correct	0 ms	348 KB	Output is correct
77	Correct	0 ms	348 KB	Output is correct
78	Correct	0 ms	348 KB	Output is correct
79	Correct	4 ms	1372 KB	Output is correct
80	Correct	372 ms	71352 KB	Output is correct
81	Correct	413 ms	70456 KB	Output is correct
82	Correct	341 ms	70840 KB	Output is correct
83	Correct	347 ms	71472 KB	Output is correct
84	Correct	351 ms	69812 KB	Output is correct
85	Correct	362 ms	71272 KB	Output is correct
86	Correct	93 ms	26840 KB	Output is correct
87	Correct	0 ms	344 KB	Output is correct