oj.uz

Submission #240502

# Submission time Handle Problem Language Result Execution time Memory
240502 2020-06-19T17:42:17 Z valerikk Strange Device (APIO19_strange_device) C++14
45 / 100
 5000 ms 221636 KB 
#include<bits/stdc++.h>
using namespace std;

/*
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
*/

template<class T = int>
inline T fast_scan() {
    T res = 0;
    char tmp;
    do tmp = getchar(); while (tmp < '0' || tmp > '9');
    while (tmp >= '0' && tmp <= '9') {
        res = res * 10 + tmp - '0';
        tmp = getchar();
    }
    return res;
}

//#define int long long
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;

#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple

#define len(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

bool inter(pll a, pll b) {
    return max(a.x, b.x) <= min(a.y, b.y);
}

pll unite(pll a, pll b) {
    return {min(a.x, b.x), max(a.y, b.y)};
}

struct Event {
    ll x;
    int type;
    ll p;

    Event() {}
    Event(ll x, int type, ll p) : x(x), type(type), p(p) {}
};

bool operator<(const Event& a, const Event& b) {
    return mt(a.x, a.type) < mt(b.x, b.type);
}

vector<Event> evs;
vector<pll> good;

void add_ev(ll l, ll r, ll p) {
    evs.eb(l, 0, p);
    evs.eb(r + 1, 1, p);
}

bool check(ll x) {
    int l = -1, r = len(good);
    while (r - l > 1) {
        int mid = (l + r) / 2;
        if (good[mid].y >= x) r = mid; else l = mid;
    }
    if (r == len(good)) return 0;
    return good[r].x <= x;
}

int32_t main() {
    int n = fast_scan();
    ll a = fast_scan<ll>(), b = fast_scan<ll>();
    ll period = a / __gcd(a, b + 1);
    for (int i = 0; i < n; ++i) {
        ll l = fast_scan<ll>(), r = fast_scan<ll>();
        ll block_l = l / b, block_r = r / b;
        if (block_l == block_r) {
            add_ev(l % b, r % b, block_l % period);
        } else {
            if (block_r - block_l > 1) {
                ll L = (block_l + 1) % period, R = (block_r - 1) % period;
                if (block_r - block_l - 1 >= period) {
                    L = 0;
                    R = period - 1;
                }
                if (L <= R) {
                    good.eb(L, R);
                } else {
                    good.eb(0, R);
                    good.eb(L, period - 1);
                }
            }
            add_ev(l % b, b - 1, block_l % period);
            add_ev(0, r % b, block_r % period);
        }
    }
    sort(all(evs));
    sort(all(good));
    vector<pll> st;
    for (auto val : good) {
        if (!st.empty() && inter(val, st.back())) st.back() = unite(st.back(), val); else st.pb(val);
    }
    good = st;
    map<int, int> cnt;
    int have = 0;
    ll ans = 0;
    for (auto val : good) ans += (val.y - val.x + 1) * b;
    for (int i = 0; i + 1 < len(evs); ++i) {
        if (!check(evs[i].p)) {
            if (evs[i].type == 0) {
                ++cnt[evs[i].p];
                if (cnt[evs[i].p] == 1) ++have;
            } else {
                --cnt[evs[i].p];
                if (cnt[evs[i].p] == 0) --have;
            }
        }
        ans += have * (evs[i + 1].x - evs[i].x);
    }
    printf("%lld", ans);
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 13 ms 1532 KB Output is correct
3 Correct 12 ms 1660 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 5 ms 384 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 256 KB Output is correct
12 Correct 5 ms 256 KB Output is correct
13 Correct 4 ms 256 KB Output is correct
14 Correct 4 ms 256 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 13 ms 1660 KB Output is correct
17 Correct 75 ms 7656 KB Output is correct
18 Correct 5 ms 256 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 6 ms 512 KB Output is correct
5 Correct 693 ms 128832 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 1134 ms 96868 KB Output is correct
3 Correct 3140 ms 221636 KB Output is correct
4 Correct 4638 ms 221404 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 1134 ms 96868 KB Output is correct
3 Correct 3140 ms 221636 KB Output is correct
4 Correct 4638 ms 221404 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 4395 ms 174536 KB Output is correct
7 Correct 1040 ms 65104 KB Output is correct
8 Correct 3547 ms 175036 KB Output is correct
9 Execution timed out 5066 ms 173912 KB Time limit exceeded

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 1134 ms 96868 KB Output is correct
3 Correct 3140 ms 221636 KB Output is correct
4 Correct 4638 ms 221404 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 172 ms 15952 KB Output is correct
7 Correct 257 ms 19080 KB Output is correct
8 Correct 287 ms 18952 KB Output is correct
9 Correct 311 ms 18956 KB Output is correct
10 Correct 181 ms 13412 KB Output is correct
11 Correct 295 ms 18952 KB Output is correct
12 Correct 314 ms 18952 KB Output is correct
13 Correct 282 ms 18956 KB Output is correct
14 Correct 73 ms 7144 KB Output is correct
15 Correct 238 ms 15960 KB Output is correct
16 Correct 102 ms 7276 KB Output is correct
17 Correct 281 ms 18312 KB Output is correct
18 Execution timed out 5081 ms 173268 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 78 ms 7140 KB Output is correct
3 Correct 102 ms 7152 KB Output is correct
4 Correct 2372 ms 101080 KB Output is correct
5 Correct 115 ms 7528 KB Output is correct
6 Correct 122 ms 7536 KB Output is correct
7 Correct 112 ms 7528 KB Output is correct
8 Correct 145 ms 8080 KB Output is correct
9 Correct 133 ms 8024 KB Output is correct
10 Correct 87 ms 7488 KB Output is correct
11 Correct 78 ms 7528 KB Output is correct
12 Correct 82 ms 7528 KB Output is correct
13 Correct 120 ms 7524 KB Output is correct
14 Correct 991 ms 51668 KB Output is correct
15 Correct 88 ms 7524 KB Output is correct
16 Correct 804 ms 50568 KB Output is correct
17 Correct 2536 ms 99964 KB Output is correct
18 Correct 5 ms 256 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 13 ms 1532 KB Output is correct
3 Correct 12 ms 1660 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 5 ms 384 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 256 KB Output is correct
12 Correct 5 ms 256 KB Output is correct
13 Correct 4 ms 256 KB Output is correct
14 Correct 4 ms 256 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 13 ms 1660 KB Output is correct
17 Correct 75 ms 7656 KB Output is correct
18 Correct 5 ms 256 KB Output is correct
19 Correct 4 ms 256 KB Output is correct
20 Correct 4 ms 256 KB Output is correct
21 Correct 4 ms 256 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 5 ms 256 KB Output is correct
24 Correct 5 ms 256 KB Output is correct
25 Correct 6 ms 512 KB Output is correct
26 Correct 5 ms 512 KB Output is correct
27 Correct 6 ms 512 KB Output is correct
28 Correct 693 ms 128832 KB Output is correct
29 Correct 4 ms 256 KB Output is correct
30 Correct 1134 ms 96868 KB Output is correct
31 Correct 3140 ms 221636 KB Output is correct
32 Correct 4638 ms 221404 KB Output is correct
33 Correct 4 ms 256 KB Output is correct
34 Correct 4395 ms 174536 KB Output is correct
35 Correct 1040 ms 65104 KB Output is correct
36 Correct 3547 ms 175036 KB Output is correct
37 Execution timed out 5066 ms 173912 KB Time limit exceeded