Submission #250124

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
250124	2020-07-17T04:20:36 Z	WhaleVomit	Strange Device (APIO19_strange_device)	C++14	35 / 100	599 ms	28248 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 = (1e18)+2000LL;
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

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	5 ms	768 KB	Output is correct
3	Correct	6 ms	1152 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct
6	Correct	0 ms	384 KB	Output is correct
7	Correct	0 ms	384 KB	Output is correct
8	Correct	0 ms	384 KB	Output is correct
9	Correct	0 ms	384 KB	Output is correct
10	Correct	0 ms	384 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	0 ms	384 KB	Output is correct
13	Correct	0 ms	384 KB	Output is correct
14	Correct	0 ms	384 KB	Output is correct
15	Correct	1 ms	384 KB	Output is correct
16	Correct	6 ms	1152 KB	Output is correct
17	Correct	57 ms	5740 KB	Output is correct
18	Incorrect	0 ms	384 KB	Output isn't correct

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 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	0 ms	384 KB	Output isn't correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	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	381 ms	22164 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	534 ms	16872 KB	Output is correct
3	Correct	517 ms	16868 KB	Output is correct
4	Correct	523 ms	16852 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	534 ms	16872 KB	Output is correct
3	Correct	517 ms	16868 KB	Output is correct
4	Correct	523 ms	16852 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct
6	Correct	515 ms	16880 KB	Output is correct
7	Correct	509 ms	16980 KB	Output is correct
8	Correct	512 ms	17008 KB	Output is correct
9	Correct	561 ms	16852 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	534 ms	16872 KB	Output is correct
3	Correct	517 ms	16868 KB	Output is correct
4	Correct	523 ms	16852 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	51 ms	2544 KB	Output is correct
7	Correct	51 ms	2544 KB	Output is correct
8	Correct	50 ms	2528 KB	Output is correct
9	Correct	50 ms	2544 KB	Output is correct
10	Correct	50 ms	2548 KB	Output is correct
11	Correct	53 ms	2544 KB	Output is correct
12	Correct	51 ms	2552 KB	Output is correct
13	Correct	54 ms	2544 KB	Output is correct
14	Correct	51 ms	2552 KB	Output is correct
15	Correct	55 ms	2544 KB	Output is correct
16	Correct	54 ms	5736 KB	Output is correct
17	Correct	53 ms	5740 KB	Output is correct
18	Correct	519 ms	28244 KB	Output is correct
19	Correct	504 ms	28248 KB	Output is correct
20	Correct	568 ms	28216 KB	Output is correct
21	Correct	54 ms	5740 KB	Output is correct
22	Correct	50 ms	5788 KB	Output is correct
23	Correct	164 ms	18528 KB	Output is correct

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	56 ms	2552 KB	Output is correct
3	Correct	62 ms	2540 KB	Output is correct
4	Correct	599 ms	16852 KB	Output is correct
5	Correct	55 ms	2540 KB	Output is correct
6	Correct	52 ms	2544 KB	Output is correct
7	Correct	56 ms	2552 KB	Output is correct
8	Correct	58 ms	2552 KB	Output is correct
9	Correct	54 ms	2544 KB	Output is correct
10	Correct	54 ms	2552 KB	Output is correct
11	Correct	53 ms	2552 KB	Output is correct
12	Correct	48 ms	2552 KB	Output is correct
13	Correct	53 ms	2544 KB	Output is correct
14	Correct	551 ms	16832 KB	Output is correct
15	Correct	55 ms	5740 KB	Output is correct
16	Correct	523 ms	28196 KB	Output is correct
17	Correct	510 ms	28116 KB	Output is correct
18	Incorrect	0 ms	384 KB	Output isn't correct

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	5 ms	768 KB	Output is correct
3	Correct	6 ms	1152 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct
6	Correct	0 ms	384 KB	Output is correct
7	Correct	0 ms	384 KB	Output is correct
8	Correct	0 ms	384 KB	Output is correct
9	Correct	0 ms	384 KB	Output is correct
10	Correct	0 ms	384 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	0 ms	384 KB	Output is correct
13	Correct	0 ms	384 KB	Output is correct
14	Correct	0 ms	384 KB	Output is correct
15	Correct	1 ms	384 KB	Output is correct
16	Correct	6 ms	1152 KB	Output is correct
17	Correct	57 ms	5740 KB	Output is correct
18	Incorrect	0 ms	384 KB	Output isn't correct

Submission #250124

Compilation message