oj.uz

Submission #211454

# Submission time Handle Problem Language Result Execution time Memory
211454 2020-03-20T11:57:49 Z VEGAnn Strange Device (APIO19_strange_device) C++14
15 / 100
 5000 ms 524292 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 = B;

        while ((fi + fi / B) % A != 0 || fi % B != 0)
            fi += B;

        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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 10 ms 1152 KB Output is correct
3 Correct 10 ms 1152 KB Output is correct
4 Correct 4 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 512 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 4 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 4 ms 384 KB Output is correct
16 Correct 12 ms 1152 KB Output is correct
17 Correct 60 ms 4856 KB Output is correct
18 Correct 5 ms 384 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Runtime error 603 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 384 KB Output is correct
5 Correct 436 ms 33344 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 536 ms 17492 KB Output is correct
3 Execution timed out 5093 ms 384 KB Time limit exceeded
4 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 Correct 536 ms 17492 KB Output is correct
3 Execution timed out 5093 ms 384 KB Time limit exceeded
4 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 Correct 536 ms 17492 KB Output is correct
3 Execution timed out 5093 ms 384 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 64 ms 5740 KB Output is correct
3 Runtime error 783 ms 524292 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 5 ms 384 KB Output is correct
2 Correct 10 ms 1152 KB Output is correct
3 Correct 10 ms 1152 KB Output is correct
4 Correct 4 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 512 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 4 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 4 ms 384 KB Output is correct
16 Correct 12 ms 1152 KB Output is correct
17 Correct 60 ms 4856 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 4 ms 384 KB Output is correct
20 Runtime error 603 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -