답안 #977369

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
977369	2024-05-07T19:43:05 Z	notyou	이상한 기계 (APIO19_strange_device)	C++17	100 / 100	377 ms	45168 KB

strange_device

#include <bits/stdc++.h>

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

#define ll long long
#define pb push_back
#define vl vector<ll>
#define fi first
#define se second
#define in insert
#define all(v) v.begin(), v.end()
#define bpc(x) __builtin_popcount(x)
#define endl "\n"

using namespace std;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const int sz = 4e5 + 5;
const int LG = 21;
// using namespace __gnu_pbds;
// tree <ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> rbt;
ll gcd(ll a, ll b){
    return __gcd(a, b);
}
ll get(ll a, ll b){
    ll c = (a / gcd(a, b + 1)), hi = inf / b;
    if(c > hi){
        c = inf;
    }
    else{
        c *= b;
    }
    return c;
}
void solve(){
    ll n, a, b, i, l, r;
    cin >> n >> a >> b;
    if(a == 1 && b == 1){
        cout << 1 << endl;
        return ;
    }
    ll x = get(a, b);
    vector<array<ll, 2>> v;
    bool ok = 1;
    for(i = 1; i <= n; i++){
        cin >> l >> r;
        ok &= ((r - l + 1) >= x);
        l %= x;
        r %= x;
        if(r < l){
            v.pb({l, x - 1});
            v.pb({0, r});
        }
        else{
            v.pb({l, r});
        }
    }
    if(ok){
        cout << x << endl;
        return ;
    }
    sort(all(v));
    ll s = 0, hi = -1;
    for(i = 0; i < v.size(); i++){
        // cout << v[i][0] << ' ' << v[i][1] << endl;
        if(v[i][0] > hi){
            s += (v[i][1] - v[i][0] + 1);
            hi = v[i][1];
        }
        else if(v[i][1] > hi){
            s += (v[i][1] - hi);
            hi = v[i][1];
        }
    }
    cout << s << endl;


}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}
/*
3 3 3
4 4
7 9
17 18
*/

Compilation message

strange_device.cpp: In function 'void solve()':
strange_device.cpp:65:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(i = 0; i < v.size(); i++){
      |                ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	3 ms	736 KB	Output is correct
3	Correct	4 ms	736 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	1 ms	344 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	344 KB	Output is correct
16	Correct	3 ms	736 KB	Output is correct
17	Correct	35 ms	2520 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	메모리	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	456 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	344 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	231 ms	17492 KB	Output is correct

Subtask #4
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	321 ms	17148 KB	Output is correct
3	Correct	316 ms	18544 KB	Output is correct
4	Correct	301 ms	17336 KB	Output is correct

Subtask #5
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	321 ms	17148 KB	Output is correct
3	Correct	316 ms	18544 KB	Output is correct
4	Correct	301 ms	17336 KB	Output is correct
5	Correct	0 ms	600 KB	Output is correct
6	Correct	306 ms	18016 KB	Output is correct
7	Correct	311 ms	17644 KB	Output is correct
8	Correct	306 ms	18264 KB	Output is correct
9	Correct	339 ms	18204 KB	Output is correct

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	321 ms	17148 KB	Output is correct
3	Correct	316 ms	18544 KB	Output is correct
4	Correct	301 ms	17336 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	31 ms	2520 KB	Output is correct
7	Correct	33 ms	2520 KB	Output is correct
8	Correct	31 ms	2520 KB	Output is correct
9	Correct	31 ms	2516 KB	Output is correct
10	Correct	31 ms	2776 KB	Output is correct
11	Correct	32 ms	2516 KB	Output is correct
12	Correct	30 ms	2516 KB	Output is correct
13	Correct	33 ms	2520 KB	Output is correct
14	Correct	30 ms	2480 KB	Output is correct
15	Correct	35 ms	2516 KB	Output is correct
16	Correct	33 ms	2520 KB	Output is correct
17	Correct	31 ms	2516 KB	Output is correct
18	Correct	314 ms	17332 KB	Output is correct
19	Correct	305 ms	18872 KB	Output is correct
20	Correct	332 ms	18948 KB	Output is correct
21	Correct	33 ms	2520 KB	Output is correct
22	Correct	28 ms	2520 KB	Output is correct
23	Correct	95 ms	10008 KB	Output is correct

Subtask #7
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	33 ms	2520 KB	Output is correct
3	Correct	35 ms	2516 KB	Output is correct
4	Correct	354 ms	17956 KB	Output is correct
5	Correct	37 ms	2520 KB	Output is correct
6	Correct	35 ms	2520 KB	Output is correct
7	Correct	35 ms	2520 KB	Output is correct
8	Correct	36 ms	2520 KB	Output is correct
9	Correct	32 ms	2520 KB	Output is correct
10	Correct	34 ms	2520 KB	Output is correct
11	Correct	34 ms	2520 KB	Output is correct
12	Correct	28 ms	2412 KB	Output is correct
13	Correct	33 ms	2424 KB	Output is correct
14	Correct	341 ms	17016 KB	Output is correct
15	Correct	33 ms	2384 KB	Output is correct
16	Correct	307 ms	17320 KB	Output is correct
17	Correct	305 ms	17436 KB	Output is correct
18	Correct	0 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	736 KB	Output is correct
3	Correct	4 ms	736 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	1 ms	344 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	344 KB	Output is correct
16	Correct	3 ms	736 KB	Output is correct
17	Correct	35 ms	2520 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 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	456 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	344 KB	Output is correct
27	Correct	1 ms	348 KB	Output is correct
28	Correct	231 ms	17492 KB	Output is correct
29	Correct	0 ms	348 KB	Output is correct
30	Correct	321 ms	17148 KB	Output is correct
31	Correct	316 ms	18544 KB	Output is correct
32	Correct	301 ms	17336 KB	Output is correct
33	Correct	0 ms	600 KB	Output is correct
34	Correct	306 ms	18016 KB	Output is correct
35	Correct	311 ms	17644 KB	Output is correct
36	Correct	306 ms	18264 KB	Output is correct
37	Correct	339 ms	18204 KB	Output is correct
38	Correct	0 ms	344 KB	Output is correct
39	Correct	31 ms	2520 KB	Output is correct
40	Correct	33 ms	2520 KB	Output is correct
41	Correct	31 ms	2520 KB	Output is correct
42	Correct	31 ms	2516 KB	Output is correct
43	Correct	31 ms	2776 KB	Output is correct
44	Correct	32 ms	2516 KB	Output is correct
45	Correct	30 ms	2516 KB	Output is correct
46	Correct	33 ms	2520 KB	Output is correct
47	Correct	30 ms	2480 KB	Output is correct
48	Correct	35 ms	2516 KB	Output is correct
49	Correct	33 ms	2520 KB	Output is correct
50	Correct	31 ms	2516 KB	Output is correct
51	Correct	314 ms	17332 KB	Output is correct
52	Correct	305 ms	18872 KB	Output is correct
53	Correct	332 ms	18948 KB	Output is correct
54	Correct	33 ms	2520 KB	Output is correct
55	Correct	28 ms	2520 KB	Output is correct
56	Correct	95 ms	10008 KB	Output is correct
57	Correct	1 ms	348 KB	Output is correct
58	Correct	33 ms	2520 KB	Output is correct
59	Correct	35 ms	2516 KB	Output is correct
60	Correct	354 ms	17956 KB	Output is correct
61	Correct	37 ms	2520 KB	Output is correct
62	Correct	35 ms	2520 KB	Output is correct
63	Correct	35 ms	2520 KB	Output is correct
64	Correct	36 ms	2520 KB	Output is correct
65	Correct	32 ms	2520 KB	Output is correct
66	Correct	34 ms	2520 KB	Output is correct
67	Correct	34 ms	2520 KB	Output is correct
68	Correct	28 ms	2412 KB	Output is correct
69	Correct	33 ms	2424 KB	Output is correct
70	Correct	341 ms	17016 KB	Output is correct
71	Correct	33 ms	2384 KB	Output is correct
72	Correct	307 ms	17320 KB	Output is correct
73	Correct	305 ms	17436 KB	Output is correct
74	Correct	0 ms	348 KB	Output is correct
75	Correct	1 ms	348 KB	Output is correct
76	Correct	0 ms	348 KB	Output is correct
77	Correct	1 ms	348 KB	Output is correct
78	Correct	0 ms	348 KB	Output is correct
79	Correct	4 ms	1116 KB	Output is correct
80	Correct	375 ms	44596 KB	Output is correct
81	Correct	377 ms	44568 KB	Output is correct
82	Correct	350 ms	44620 KB	Output is correct
83	Correct	357 ms	44720 KB	Output is correct
84	Correct	342 ms	44600 KB	Output is correct
85	Correct	369 ms	45168 KB	Output is correct
86	Correct	103 ms	17804 KB	Output is correct
87	Correct	0 ms	348 KB	Output is correct