oj.uz

Submission #211459

# Submission time Handle Problem Language Result Execution time Memory
211459 2020-03-20T12:07:16 Z VEGAnn Strange Device (APIO19_strange_device) C++14
30 / 100
 797 ms 524288 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;
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;

    if (B <= ll(1e6)){

        ll fi = A * B;

        if (fi % 2 == 0){

            fi >>= 1;
            if ((fi + fi / B) % A != 0 || fi % B != 0)
                fi <<= 1;
        }

        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;
    }

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

        for (ll t = l; t <= r; t++)
            vc.PB(MP((t + t / B) % A, t % B));
    }

    sort(all(vc));
    vc.resize(unique(all(vc)) - vc.begin());

    cout << sz(vc);

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 10 ms 1144 KB Output is correct
3 Correct 10 ms 1152 KB Output is correct
4 Incorrect 4 ms 384 KB Output isn't correct
5 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 Runtime error 591 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
5.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 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 512 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 500 ms 17108 KB Output is correct
3 Correct 493 ms 16852 KB Output is correct
4 Correct 528 ms 53312 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 500 ms 17108 KB Output is correct
3 Correct 493 ms 16852 KB Output is correct
4 Correct 528 ms 53312 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 512 ms 53464 KB Output is correct
7 Correct 520 ms 53568 KB Output is correct
8 Incorrect 553 ms 53312 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 500 ms 17108 KB Output is correct
3 Correct 493 ms 16852 KB Output is correct
4 Correct 528 ms 53312 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 53 ms 5736 KB Output is correct
7 Correct 58 ms 5740 KB Output is correct
8 Correct 52 ms 5740 KB Output is correct
9 Correct 53 ms 5740 KB Output is correct
10 Correct 57 ms 5868 KB Output is correct
11 Correct 57 ms 5740 KB Output is correct
12 Correct 54 ms 5740 KB Output is correct
13 Correct 58 ms 5740 KB Output is correct
14 Correct 54 ms 5864 KB Output is correct
15 Correct 59 ms 5732 KB Output is correct
16 Correct 57 ms 5736 KB Output is correct
17 Correct 57 ms 5908 KB Output is correct
18 Correct 523 ms 53464 KB Output is correct
19 Correct 510 ms 53404 KB Output is correct
20 Correct 560 ms 53312 KB Output is correct
21 Correct 57 ms 5780 KB Output is correct
22 Correct 54 ms 5740 KB Output is correct
23 Correct 182 ms 26704 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 59 ms 2540 KB Output is correct
3 Runtime error 797 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

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