oj.uz

Submission #211469

# Submission time Handle Problem Language Result Execution time Memory
211469 2020-03-20T12:53:09 Z VEGAnn Strange Device (APIO19_strange_device) C++14
0 / 100
 667 ms 17264 KB 
#include <bits/stdc++.h>
#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> vc;
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;

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

    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 384 KB Output is correct
2 Incorrect 10 ms 1024 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
0 / 5.0

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

Subtask #4
0 / 5.0

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 505 ms 17264 KB Output isn't correct
3 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 60 ms 3056 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 384 KB Output is correct
2 Incorrect 10 ms 1024 KB Output isn't correct
3 Halted 0 ms 0 KB -