답안 #781535

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
781535	2023-07-13T07:42:32 Z	kebine	이상한 기계 (APIO19_strange_device)	C++17	65 / 100	391 ms	93488 KB

strange_device

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define fi first
#define se second

ll l[1000005], r[1000005];
vector<pair<ll, ll>> v, ans;

int main() { 
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    /*
    t = xb;
    xb + x = y * a
    x * (b + 1) = y * a
    x = lcm(b + 1, a) / (b + 1)
    a/gcd(b + 1, a) = lcm(b + 1, a) / (b + 1);
    x = a/gcd(b + 1, a)
    banyaknya possibility = x * b -> x = a / gcd(b + 1, a);
    x * b >= r
    b / x
    */
    int n;
    ll a, b;
    cin >> n >> a >> b;
    ll x = a / gcd(b + 1, a), sum = 0, ans1 = 0;
    for (int i = 1; i <= n; i++) {
        cin >> l[i] >> r[i];
        sum += r[i] - l[i] + 1;
    }
    if (r[n - 1] / x < b) {
        cout << sum << "\n";
        return 0;
    }
    for (int i = 1; i <= n; i++) {
        if (r[i] - l[i] + 1 >= x * b) {
            cout << x * b;
            return 0;
        }
        l[i] %= (x * b), r[i] %= (x * b);
        if (l[i] <= r[i]) v.push_back({l[i], r[i]});
        else v.push_back({l[i], x * b - 1}), v.push_back({0, r[i]});
    }
    sort(v.begin(), v.end());
    for (int i = 0; i < (int)v.size(); i++) {
        if (ans.empty()) {
            ans.push_back(v[i]);
            continue;
        }
        if (v[i].fi > ans.back().se) ans.push_back(v[i]);
        else ans.back().se = max(ans.back().se, v[i].se);
    }  
    for (auto u : ans) ans1 += u.se - u.fi + 1;
    cout << ans1 << "\n";
}

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	4 ms	984 KB	Output is correct
3	Correct	4 ms	984 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	4 ms	984 KB	Output is correct
17	Correct	35 ms	6552 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct

Subtask #2
0 / 5.0

#	결과	메모리	Grader output
1	Correct	212 KB	Output is correct
2	Incorrect	212 KB	Output isn't correct
3	Halted	0 KB	-

Subtask #3
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	220 ms	33120 KB	Output is correct

Subtask #4
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	318 ms	56216 KB	Output is correct
3	Correct	337 ms	93480 KB	Output is correct
4	Correct	314 ms	93400 KB	Output is correct

Subtask #5
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	318 ms	56216 KB	Output is correct
3	Correct	337 ms	93480 KB	Output is correct
4	Correct	314 ms	93400 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	321 ms	93336 KB	Output is correct
7	Correct	341 ms	93400 KB	Output is correct
8	Correct	335 ms	93336 KB	Output is correct
9	Correct	342 ms	93440 KB	Output is correct

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	318 ms	56216 KB	Output is correct
3	Correct	337 ms	93480 KB	Output is correct
4	Correct	314 ms	93400 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	33 ms	10256 KB	Output is correct
7	Correct	34 ms	10148 KB	Output is correct
8	Correct	32 ms	10164 KB	Output is correct
9	Correct	37 ms	10272 KB	Output is correct
10	Correct	32 ms	10184 KB	Output is correct
11	Correct	34 ms	10236 KB	Output is correct
12	Correct	31 ms	10180 KB	Output is correct
13	Correct	33 ms	10192 KB	Output is correct
14	Correct	31 ms	10152 KB	Output is correct
15	Correct	35 ms	10164 KB	Output is correct
16	Correct	35 ms	10228 KB	Output is correct
17	Correct	33 ms	10200 KB	Output is correct
18	Correct	331 ms	93488 KB	Output is correct
19	Correct	334 ms	93432 KB	Output is correct
20	Correct	352 ms	93452 KB	Output is correct
21	Correct	34 ms	10180 KB	Output is correct
22	Correct	31 ms	10160 KB	Output is correct
23	Correct	97 ms	26536 KB	Output is correct

Subtask #7
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	33 ms	6468 KB	Output is correct
3	Correct	35 ms	10200 KB	Output is correct
4	Correct	391 ms	93420 KB	Output is correct
5	Correct	40 ms	10352 KB	Output is correct
6	Correct	34 ms	10236 KB	Output is correct
7	Correct	35 ms	10204 KB	Output is correct
8	Correct	35 ms	10244 KB	Output is correct
9	Correct	34 ms	10180 KB	Output is correct
10	Correct	44 ms	10180 KB	Output is correct
11	Correct	34 ms	10204 KB	Output is correct
12	Correct	30 ms	10204 KB	Output is correct
13	Correct	41 ms	10264 KB	Output is correct
14	Correct	360 ms	93380 KB	Output is correct
15	Correct	35 ms	10264 KB	Output is correct
16	Correct	364 ms	93392 KB	Output is correct
17	Correct	363 ms	93392 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct

Subtask #8
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	4 ms	984 KB	Output is correct
3	Correct	4 ms	984 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	4 ms	984 KB	Output is correct
17	Correct	35 ms	6552 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Incorrect	0 ms	212 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

답안 #781535

Compilation message