oj.uz

답안 #250122

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
250122 2020-07-17T04:11:52 Z WhaleVomit 이상한 기계 (APIO19_strange_device) C++14
10 / 100
 627 ms 21460 KB 
#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 = 1e18+5;
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 >= 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 {
            res += interval.s - last;
        }
        last = interval.s;
    }
    finish(res);
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 Incorrect 1 ms 384 KB Output isn't correct

Subtask #3
0 / 5.0

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

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 520 ms 17752 KB Output is correct
3 Correct 504 ms 17776 KB Output is correct
4 Correct 495 ms 17752 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 17752 KB Output is correct
3 Correct 504 ms 17776 KB Output is correct
4 Correct 495 ms 17752 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 530 ms 17916 KB Output is correct
7 Correct 530 ms 17964 KB Output is correct
8 Correct 508 ms 17748 KB Output is correct
9 Correct 551 ms 17752 KB Output is correct

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 520 ms 17752 KB Output is correct
3 Correct 504 ms 17776 KB Output is correct
4 Correct 495 ms 17752 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 51 ms 2936 KB Output is correct
7 Correct 55 ms 5360 KB Output is correct
8 Correct 54 ms 5232 KB Output is correct
9 Correct 51 ms 5240 KB Output is correct
10 Correct 54 ms 5352 KB Output is correct
11 Correct 52 ms 5356 KB Output is correct
12 Correct 51 ms 5352 KB Output is correct
13 Correct 57 ms 5356 KB Output is correct
14 Correct 52 ms 5348 KB Output is correct
15 Incorrect 57 ms 5356 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 55 ms 5236 KB Output is correct
3 Correct 56 ms 5356 KB Output is correct
4 Correct 627 ms 21292 KB Output is correct
5 Correct 58 ms 5348 KB Output is correct
6 Correct 56 ms 5356 KB Output is correct
7 Correct 53 ms 5352 KB Output is correct
8 Correct 55 ms 5352 KB Output is correct
9 Correct 53 ms 5364 KB Output is correct
10 Correct 54 ms 5356 KB Output is correct
11 Correct 56 ms 5232 KB Output is correct
12 Correct 49 ms 5348 KB Output is correct
13 Correct 54 ms 5232 KB Output is correct
14 Incorrect 554 ms 21460 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

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