답안 #250163

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
250163	2020-07-17T05:28:56 Z	WhaleVomit	이상한 기계 (APIO19_strange_device)	C++14	35 / 100	584 ms	24512 KB

strange_device

#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define sz(v) (int)v.size()

#define MOO(i, a, b) for(int i=a; i<b; i++)
#define M00(i, a) for(int i=0; i<a; i++)
#define MOOd(i,a,b) for(int i = (b)-1; i >= a; i--)
#define M00d(i,a) for(int i = (a)-1; i>=0; i--)

#define FAST ios::sync_with_stdio(0); cin.tie(0);
#define finish(x) return cout << x << '\n', 0;
#define dbg(x) cerr << ">>> " << #x << " = " << x << "\n";
#define _ << " _ " <<

template<class T> bool ckmin(T& a, const T& b) {return b < a ? a = b, 1 : 0;}
template<class T> bool ckmax(T& a, const T& b) {return a < b ? a = b, 1 : 0;}

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef pair<ld,ld> pd;
typedef complex<ld> cd;

const int MAX_N = 1000010;
const ll inf = (ll)(2e18);
int n;
ll A, B;

ll gcd(ll a, ll b) {
    if(a > b) swap(a,b);
    if(a == 0) return b;
    return gcd(b%a, a);
}

bool overflow(ll a, ll b) {
    ll val = a*b;
    if(val / b == a) return 0;
    return 1;
}

int main() { FAST
    cin >> n >> A >> B;
    ll period = A/gcd(A,B+1);
    if(overflow(B, period)) {
        period = inf;
    } else {
        period = B * period;
    }
    vector<pair<ll,ll>> intervals;
    M00(i, n) {
        ll l, r; cin >> l >> r;
        if(r-l+1 >= period) {
            finish(period);
        }
        l %= period;
        r %= period;
        if(l <= r) intervals.pb(mp(l, r));
        else {
            intervals.pb(mp(l, period-1));
            intervals.pb(mp(0,r));
        }
    }
    sort(all(intervals));
    ll last = -1;
    ll res = 0;
    for(pair<ll,ll> interval: intervals) {
        if(interval.f > last) {
            res += interval.s - interval.f + 1;
        } else {
            if(interval.s > last) res += interval.s - last;
        }
        ckmax(last, interval.s);
    }
    finish(res);
}

Subtask #1
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	6 ms	768 KB	Output is correct
3	Correct	6 ms	768 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct
6	Correct	1 ms	384 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	0 ms	384 KB	Output is correct
11	Correct	0 ms	384 KB	Output is correct
12	Correct	0 ms	384 KB	Output is correct
13	Correct	1 ms	384 KB	Output is correct
14	Correct	1 ms	384 KB	Output is correct
15	Correct	0 ms	384 KB	Output is correct
16	Correct	6 ms	768 KB	Output is correct
17	Correct	55 ms	2672 KB	Output is correct
18	Incorrect	1 ms	384 KB	Output isn't correct

Subtask #2
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Incorrect	1 ms	384 KB	Output isn't correct

Subtask #3
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	376 ms	19960 KB	Output is correct

Subtask #4
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	520 ms	17108 KB	Output is correct
3	Correct	527 ms	24068 KB	Output is correct
4	Correct	501 ms	24404 KB	Output is correct

Subtask #5
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	520 ms	17108 KB	Output is correct
3	Correct	527 ms	24068 KB	Output is correct
4	Correct	501 ms	24404 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	517 ms	24500 KB	Output is correct
7	Correct	505 ms	24404 KB	Output is correct
8	Correct	514 ms	24512 KB	Output is correct
9	Correct	563 ms	24408 KB	Output is correct

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	520 ms	17108 KB	Output is correct
3	Correct	527 ms	24068 KB	Output is correct
4	Correct	501 ms	24404 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct
6	Correct	56 ms	5740 KB	Output is correct
7	Correct	58 ms	5356 KB	Output is correct
8	Correct	51 ms	5356 KB	Output is correct
9	Correct	54 ms	5368 KB	Output is correct
10	Correct	51 ms	5356 KB	Output is correct
11	Correct	58 ms	5356 KB	Output is correct
12	Correct	52 ms	5352 KB	Output is correct
13	Correct	55 ms	5356 KB	Output is correct
14	Correct	50 ms	5352 KB	Output is correct
15	Correct	55 ms	5356 KB	Output is correct
16	Correct	54 ms	5232 KB	Output is correct
17	Correct	55 ms	5232 KB	Output is correct
18	Correct	505 ms	19672 KB	Output is correct
19	Correct	491 ms	19668 KB	Output is correct
20	Correct	571 ms	19672 KB	Output is correct
21	Correct	65 ms	5232 KB	Output is correct
22	Correct	50 ms	5232 KB	Output is correct
23	Correct	169 ms	9016 KB	Output is correct

Subtask #7
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	52 ms	2672 KB	Output is correct
3	Correct	56 ms	5480 KB	Output is correct
4	Correct	584 ms	23764 KB	Output is correct
5	Correct	57 ms	5428 KB	Output is correct
6	Correct	56 ms	5356 KB	Output is correct
7	Correct	56 ms	5352 KB	Output is correct
8	Correct	58 ms	5356 KB	Output is correct
9	Correct	55 ms	5352 KB	Output is correct
10	Correct	69 ms	5356 KB	Output is correct
11	Correct	57 ms	5360 KB	Output is correct
12	Correct	61 ms	5352 KB	Output is correct
13	Correct	57 ms	5356 KB	Output is correct
14	Correct	566 ms	23764 KB	Output is correct
15	Correct	55 ms	5232 KB	Output is correct
16	Correct	515 ms	19672 KB	Output is correct
17	Correct	491 ms	19668 KB	Output is correct
18	Incorrect	0 ms	384 KB	Output isn't correct

Subtask #8
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	6 ms	768 KB	Output is correct
3	Correct	6 ms	768 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct
6	Correct	1 ms	384 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	0 ms	384 KB	Output is correct
11	Correct	0 ms	384 KB	Output is correct
12	Correct	0 ms	384 KB	Output is correct
13	Correct	1 ms	384 KB	Output is correct
14	Correct	1 ms	384 KB	Output is correct
15	Correct	0 ms	384 KB	Output is correct
16	Correct	6 ms	768 KB	Output is correct
17	Correct	55 ms	2672 KB	Output is correct
18	Incorrect	1 ms	384 KB	Output isn't correct

답안 #250163

Compilation message