oj.uz

Submission #211472

# Submission time Handle Problem Language Result Execution time Memory
211472 2020-03-20T13:02:53 Z VEGAnn Strange Device (APIO19_strange_device) C++14
10 / 100
 533 ms 17048 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("fast-math")
#pragma GCC optimize("no-stack-protector")
#define ft first
#define sd second
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define pll pair<ll, ll>
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long ll;
//typedef long long __int128;
vector<pll> seg;
int n;
ll A, B;

int main(){

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#else
    ios_base::sync_with_stdio(0); cin.tie(0);
#endif // _LOCAL

    cin >> n >> A >> B;

//    ll fi = 1;
//
//    while ((fi + fi / B) % A != 0 || fi % B != 0)
//        fi++;
//
//    cout << fi << '\n';

    ll fi = A;

    if (A >= B) {

        while (fi <= ll(1e18) && fi % (B + 1) > 0)
            fi += A;

        if (fi <= ll(1e18))
            fi -= fi / (B + 1);

    } else {
        while (fi <= ll(1e18) && ((fi + fi / B) % A != 0))
            fi += B;
    }

//    cout << fi << '\n';

    seg.clear();

    for (int i = 0; i < n; i++){
        ll l, r; cin >> l >> r;

        if (r - l + 1 >= fi){
            seg.PB(MP(0, fi - 1));
            continue;
        }

        ll vl = ((l - 1) / fi) * fi + fi;

        if (vl > r){
            vl -= fi;
            seg.PB(MP(l - vl, r - vl));
        } else {
            vl -= fi;
            seg.PB(MP(l - vl, fi - 1));
            vl += fi;
            seg.PB(MP(0ll, r - vl));
        }
    }

    sort(all(seg));

    ll lst = -1, ans = 0;

    for (pll cr : seg)
        if (cr.ft > lst){
            ans += cr.sd - cr.ft + 1ll;
            lst = cr.sd;
        } else {

            ans += max(lst, cr.sd) - lst;
            lst = max(lst, cr.sd);
        }

    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 Incorrect 9 ms 768 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
0 / 5.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 504 ms 16980 KB Output is correct
3 Correct 504 ms 16984 KB Output is correct
4 Correct 488 ms 16980 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 504 ms 16980 KB Output is correct
3 Correct 504 ms 16984 KB Output is correct
4 Correct 488 ms 16980 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 507 ms 17048 KB Output is correct
7 Correct 506 ms 16980 KB Output is correct
8 Correct 500 ms 16980 KB Output is correct
9 Correct 533 ms 16976 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 504 ms 16980 KB Output is correct
3 Correct 504 ms 16984 KB Output is correct
4 Correct 488 ms 16980 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 51 ms 2676 KB Output is correct
7 Correct 56 ms 2544 KB Output is correct
8 Correct 51 ms 2672 KB Output is correct
9 Correct 56 ms 2672 KB Output is correct
10 Correct 54 ms 2672 KB Output is correct
11 Correct 59 ms 2820 KB Output is correct
12 Correct 54 ms 2680 KB Output is correct
13 Correct 58 ms 2680 KB Output is correct
14 Incorrect 49 ms 2672 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Incorrect 55 ms 2680 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Incorrect 9 ms 768 KB Output isn't correct
3 Halted 0 ms 0 KB -