Submission #240097

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
240097	2020-06-18T02:28:48 Z	wiwiho	Strange Device (APIO19_strange_device)	C++14	35 / 100	802 ms	33568 KB

strange_device

//#define NDEBUG

#include <bits/stdc++.h>
#include <bits/extc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define iceil(a, b) ((a + b - 1) / b)
#define tomax(a, b) (a = max(a, b))
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; pvaspace=true;\
    b << pva;\
}\
b << "\n";}

//#define TEST

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;

const ll MOD = 1000000007;
const ll MAX = 2147483647;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

int main(){
    StarBurstStream

    int n;
    cin >> n;

    ll a, b;
    cin >> a >> b;

    ll x = a / __gcd(a, b + 1);
    ll t = x * b;

    vector<pll> e;
    for(int i = 0; i < n; i++){

        ll l, r;
        cin >> l >> r;

        if(r - l + 1 >= t){
            cout << t << "\n";
            return 0;
        }

        if(l % t <= r % t){
            e.eb(mp(l % t, 1));
            e.eb(mp(r % t + 1, 0));
        }
        else{
            e.eb(mp(l % t, 1));
            e.eb(mp(t, 0));
            e.eb(mp(0, 1));
            e.eb(mp(r % t + 1, 0));
        }
    }

    cerr << t << "\n";

    ll ans = 0, lst = -1;
    int cnt = 0;
    lsort(e);

    for(pll i : e){
//        cerr << i.F << " " << i.S << " " << lst << "\n";
        if(i.S){
            cnt++;
            if(lst == -1) lst = i.F;
        }
        else{
            cnt--;
            if(cnt == 0){
//                cerr << "test " << lst << " " << i.F << "\n";
                ans += i.F - lst;
                lst = -1;
            }
        }
//        cerr << cnt << " " << ans << "\n";
    }

    cout << ans << "\n";

    return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	4 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Incorrect	5 ms	384 KB	Output isn't correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	5 ms	436 KB	Output is correct
5	Correct	436 ms	33344 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	614 ms	33320 KB	Output is correct
3	Correct	641 ms	33340 KB	Output is correct
4	Correct	658 ms	33300 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	614 ms	33320 KB	Output is correct
3	Correct	641 ms	33340 KB	Output is correct
4	Correct	658 ms	33300 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	657 ms	33344 KB	Output is correct
7	Correct	643 ms	33324 KB	Output is correct
8	Correct	632 ms	33320 KB	Output is correct
9	Correct	741 ms	33344 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	614 ms	33320 KB	Output is correct
3	Correct	641 ms	33340 KB	Output is correct
4	Correct	658 ms	33300 KB	Output is correct
5	Correct	4 ms	384 KB	Output is correct
6	Correct	67 ms	4584 KB	Output is correct
7	Correct	66 ms	4588 KB	Output is correct
8	Correct	63 ms	4588 KB	Output is correct
9	Correct	71 ms	4596 KB	Output is correct
10	Correct	60 ms	4596 KB	Output is correct
11	Correct	72 ms	4560 KB	Output is correct
12	Correct	94 ms	4584 KB	Output is correct
13	Correct	84 ms	4584 KB	Output is correct
14	Correct	65 ms	4596 KB	Output is correct
15	Correct	75 ms	4588 KB	Output is correct
16	Correct	72 ms	4584 KB	Output is correct
17	Correct	66 ms	4588 KB	Output is correct
18	Correct	636 ms	33280 KB	Output is correct
19	Correct	618 ms	33348 KB	Output is correct
20	Correct	776 ms	33348 KB	Output is correct
21	Correct	82 ms	4584 KB	Output is correct
22	Correct	59 ms	4596 KB	Output is correct
23	Correct	208 ms	16856 KB	Output is correct

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	77 ms	4584 KB	Output is correct
3	Correct	71 ms	4588 KB	Output is correct
4	Correct	802 ms	33568 KB	Output is correct
5	Correct	70 ms	4584 KB	Output is correct
6	Correct	90 ms	4588 KB	Output is correct
7	Correct	71 ms	4588 KB	Output is correct
8	Correct	76 ms	4588 KB	Output is correct
9	Correct	81 ms	4588 KB	Output is correct
10	Correct	74 ms	4596 KB	Output is correct
11	Correct	71 ms	4588 KB	Output is correct
12	Correct	64 ms	4596 KB	Output is correct
13	Correct	76 ms	4584 KB	Output is correct
14	Correct	719 ms	33344 KB	Output is correct
15	Correct	75 ms	4596 KB	Output is correct
16	Correct	624 ms	33348 KB	Output is correct
17	Correct	622 ms	33344 KB	Output is correct
18	Incorrect	4 ms	384 KB	Output isn't correct

Subtask #8
0 / 30.0

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

Submission #240097

Compilation message