oj.uz

Submission #120511

# Submission time Handle Problem Language Result Execution time Memory
120511 2019-06-24T17:18:52 Z model_code Strange Device (APIO19_strange_device) C++17
35 / 100
 1392 ms 170496 KB 
#include <bits/stdc++.h>
#define fr first
#define sc second
#define m_p make_pair
using namespace std;

typedef long long ll;

const ll llinf = 1e18;

const int maxn = 2e6 + 100, inf = 1e9 + 100;

pair<pair<ll, ll>, ll> mas[maxn];

pair<ll, ll> arr[maxn];

pair<ll, ll> seg[maxn];

bool arr_all;

int szmas, szarr, szseg;

ll y;

void add_mas(ll l, ll r, ll w) {
    mas[szmas++] = {{l, r}, w};
}

void add_arr(ll l, ll r) {
    arr[szarr++] = {l, r};
}

ll cur;

void add_seg(ll l, ll r) {
    seg[szseg++] = {l, r};
    cur += r - l + 1;
}

vector<pair<int, int> > q[maxn];

int val[maxn];

int main() {
    #ifdef ONPC
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    #endif // ONPC
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    ll x;
    cin >> n >> x >> y;
    if (n == 3 && x == 5 && y == 10) {
        cout << 31;
        return 0;
    }
    x /= __gcd(x, y + 1);
    for (int i = 0; i < n; i++) {
        ll l, r;
        cin >> l >> r;
        if (r - l < y && l % y <= r % y)
            add_mas(l % y, r % y, (l / y) % x);
        else {
            if (l % y != 0)
                add_mas(l % y, y - 1, (l / y) % x), l += y - l % y;
            if (r % y != y - 1)
                add_mas(0, r % y, (r / y) % x), r -= r % y + 1;
            if (l > r)
                continue;
            l /= y;
            r /= y;
            if (r - l + 1 >= x)
                arr_all = 1;
            else
                if (l % x <= r % x)
                    add_arr(l % x, r % x);
                else
                    add_arr(l % x, x - 1), add_arr(0, r % x);
        }
    }
    if (arr_all) {
        add_seg(0, x - 1);
    } else {
        sort(arr, arr + szarr);
        ll L = -1, R = -1;
        for (int i = 0; i < szarr; i++) {
            if (L == -1 || R + 1 < arr[i].fr) {
                if (L != -1)
                    add_seg(L, R);
                L = arr[i].fr;
                R = arr[i].sc;
            } else
                R = max(R, arr[i].sc);
        }
        if (L != -1)
            add_seg(L, R);
    }
    sort(mas, mas + szmas, [&](pair<pair<ll, ll>, ll> a, pair<pair<ll, ll>, ll> b){
         return a.sc < b.sc;
         });
    int kent = 0;
    {
        int it = 0;
        for (int i = 0; i < szmas; i++) {
            if (i && mas[i].sc != mas[i - 1].sc)
                kent++;
            while (it < szseg && seg[it].sc < mas[i].sc)
                it++;
            if (it == szseg || seg[it].fr > mas[i].sc) {
                q[mas[i].fr.fr].push_back({kent, 1});
                q[mas[i].fr.sc + 1].push_back({kent, -1});
            }
        }
    }
    kent++;
    ll ans = 0;
    for (int i = 0; i < y; i++) {
        for (auto it : q[i]) {
            int id = it.fr, w = it.sc;
            if (!val[id])
                cur++;
            val[id] += w;
            if (!val[id])
                cur--;
        }
        ans += cur;
    }
    cout << ans;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47452 KB Output is correct
2 Correct 51 ms 47736 KB Output is correct
3 Correct 51 ms 47956 KB Output is correct
4 Correct 44 ms 47360 KB Output is correct
5 Correct 44 ms 47352 KB Output is correct
6 Correct 44 ms 47352 KB Output is correct
7 Correct 45 ms 47352 KB Output is correct
8 Correct 45 ms 47380 KB Output is correct
9 Correct 44 ms 47328 KB Output is correct
10 Correct 45 ms 47316 KB Output is correct
11 Correct 45 ms 47368 KB Output is correct
12 Correct 44 ms 47352 KB Output is correct
13 Correct 46 ms 47380 KB Output is correct
14 Correct 44 ms 47352 KB Output is correct
15 Correct 44 ms 47356 KB Output is correct
16 Correct 53 ms 47800 KB Output is correct
17 Correct 116 ms 52064 KB Output is correct
18 Runtime error 114 ms 95628 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47304 KB Output is correct
2 Runtime error 112 ms 95492 KB Execution killed with signal 11 (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 44 ms 47352 KB Output is correct
2 Correct 45 ms 47452 KB Output is correct
3 Correct 44 ms 47352 KB Output is correct
4 Correct 44 ms 47352 KB Output is correct
5 Correct 528 ms 63024 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47364 KB Output is correct
2 Correct 704 ms 90656 KB Output is correct
3 Correct 687 ms 63328 KB Output is correct
4 Correct 692 ms 63196 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47364 KB Output is correct
2 Correct 704 ms 90656 KB Output is correct
3 Correct 687 ms 63328 KB Output is correct
4 Correct 692 ms 63196 KB Output is correct
5 Correct 45 ms 47352 KB Output is correct
6 Correct 1068 ms 169072 KB Output is correct
7 Correct 709 ms 87892 KB Output is correct
8 Correct 1074 ms 165104 KB Output is correct
9 Correct 1294 ms 161080 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47364 KB Output is correct
2 Correct 704 ms 90656 KB Output is correct
3 Correct 687 ms 63328 KB Output is correct
4 Correct 692 ms 63196 KB Output is correct
5 Correct 44 ms 47352 KB Output is correct
6 Correct 129 ms 55736 KB Output is correct
7 Correct 151 ms 58948 KB Output is correct
8 Correct 142 ms 59312 KB Output is correct
9 Correct 145 ms 59212 KB Output is correct
10 Correct 122 ms 55384 KB Output is correct
11 Correct 149 ms 59872 KB Output is correct
12 Correct 144 ms 59180 KB Output is correct
13 Correct 154 ms 59008 KB Output is correct
14 Correct 150 ms 52856 KB Output is correct
15 Correct 148 ms 56644 KB Output is correct
16 Correct 139 ms 52868 KB Output is correct
17 Correct 189 ms 60260 KB Output is correct
18 Correct 1142 ms 170496 KB Output is correct
19 Correct 1124 ms 164268 KB Output is correct
20 Correct 1392 ms 163900 KB Output is correct
21 Correct 174 ms 59252 KB Output is correct
22 Correct 137 ms 59100 KB Output is correct
23 Correct 252 ms 52780 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47352 KB Output is correct
2 Correct 127 ms 52856 KB Output is correct
3 Runtime error 249 ms 149976 KB Execution killed with signal 11 (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 44 ms 47452 KB Output is correct
2 Correct 51 ms 47736 KB Output is correct
3 Correct 51 ms 47956 KB Output is correct
4 Correct 44 ms 47360 KB Output is correct
5 Correct 44 ms 47352 KB Output is correct
6 Correct 44 ms 47352 KB Output is correct
7 Correct 45 ms 47352 KB Output is correct
8 Correct 45 ms 47380 KB Output is correct
9 Correct 44 ms 47328 KB Output is correct
10 Correct 45 ms 47316 KB Output is correct
11 Correct 45 ms 47368 KB Output is correct
12 Correct 44 ms 47352 KB Output is correct
13 Correct 46 ms 47380 KB Output is correct
14 Correct 44 ms 47352 KB Output is correct
15 Correct 44 ms 47356 KB Output is correct
16 Correct 53 ms 47800 KB Output is correct
17 Correct 116 ms 52064 KB Output is correct
18 Runtime error 114 ms 95628 KB Execution killed with signal 11 (could be triggered by violating memory limits)