oj.uz

Submission #240416

# Submission time Handle Problem Language Result Execution time Memory
240416 2020-06-19T15:15:06 Z valerikk Strange Device (APIO19_strange_device) C++17
25 / 100
 5000 ms 508428 KB 
#include<bits/stdc++.h>
using namespace std;

#define ll long long

ll gcd(ll a, ll b) {
    while (b != 0LL) {
        a %= b;
        swap(a, b);
    }
    return a;
}

struct E {
    ll x;
    int k;
    ll l, r;

    bool operator<(const E& o) {
        return x < o.x || (x == o.x && k < o.k);
    }

    E() {}
    E(ll x, int k, ll l, ll r) : x(x), k(k), l(l), r(r) {}
};

ll n, a, b;

ll p;

vector<E> v;

void push(ll l, ll r, ll x, ll y) {
    v.emplace_back(l, 0, x, y);
    v.emplace_back(r+1, 1, x, y);
}

void add(ll l, ll r, ll x, ll y) {
    if (x <= y) {
        push(l, r, x, y);
    } else {
        push(l, r, 0LL, y);
        push(l, r, x, p-1LL);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> a >> b;
    p = a/gcd(a, b+1);
    while (n--) {
        ll l, r;
        cin >> l >> r;
        ll x = l/b, y = r/b;
        if (x == y) {
            add(l%b, r%b, x%p, y%p);
        } else {
            if (y-x > 1) {
                add(0LL, b-1LL, (x+1LL)%p, (y-1LL)%p);
            }
            add(l%b, b-1LL, x%p, x%p);
            add(0LL, r%b, y%p, y%p);
        }
    }
    sort(v.begin(), v.end());
    multiset<pair<ll, ll>> s;
    ll ans = 0;
    for (int i = 0; i+1 < v.size(); ++i) {
        if (v[i].k) {
            s.erase(s.find({v[i].l, v[i].r}));
        } else {
            s.insert({v[i].l, v[i].r});
        }
        ll d = v[i+1].x-v[i].x;
        if (d) {
            vector<pair<ll, ll>> u;
            for (auto ss : s) {
                u.emplace_back(ss.first, 1);
                u.emplace_back(ss.second+1, -1);
            }
            sort(u.begin(), u.end());
            ll q = 0;
            int bal = 0;
            for (int j = 0; j+1 < u.size(); ++j) {
                bal += u[j].second;
                if (bal) q += u[j+1].first-u[j].first;
            }
            ans += q*d;
        }
    }
    cout << ans;
    return 0;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:69:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i+1 < v.size(); ++i) {
                     ~~~~^~~~~~~~~~
strange_device.cpp:85:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j+1 < u.size(); ++j) {
                             ~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 18 ms 1532 KB Output is correct
3 Correct 18 ms 1532 KB Output is correct
4 Correct 5 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 384 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 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 8 ms 384 KB Output is correct
16 Correct 18 ms 1532 KB Output is correct
17 Correct 98 ms 8680 KB Output is correct
18 Correct 4 ms 384 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Incorrect 5 ms 384 KB Output isn't correct
5 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 16 ms 768 KB Output is correct
3 Correct 10 ms 512 KB Output is correct
4 Correct 39 ms 512 KB Output is correct
5 Correct 2376 ms 507764 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 1099 ms 175708 KB Output is correct
3 Correct 2527 ms 508388 KB Output is correct
4 Correct 2581 ms 508428 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 1099 ms 175708 KB Output is correct
3 Correct 2527 ms 508388 KB Output is correct
4 Correct 2581 ms 508428 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 3401 ms 442260 KB Output is correct
7 Correct 1320 ms 130116 KB Output is correct
8 Correct 3873 ms 443156 KB Output is correct
9 Correct 3720 ms 446208 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 1099 ms 175708 KB Output is correct
3 Correct 2527 ms 508388 KB Output is correct
4 Correct 2581 ms 508428 KB Output is correct
5 Correct 5 ms 432 KB Output is correct
6 Correct 379 ms 31168 KB Output is correct
7 Correct 507 ms 50972 KB Output is correct
8 Correct 479 ms 50976 KB Output is correct
9 Correct 483 ms 50848 KB Output is correct
10 Correct 1215 ms 25032 KB Output is correct
11 Correct 3493 ms 49296 KB Output is correct
12 Correct 3589 ms 50960 KB Output is correct
13 Correct 2715 ms 55024 KB Output is correct
14 Correct 149 ms 11364 KB Output is correct
15 Execution timed out 5047 ms 29956 KB Time limit exceeded
16 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 1002 ms 11368 KB Output is correct
3 Execution timed out 5051 ms 11240 KB Time limit exceeded
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 18 ms 1532 KB Output is correct
3 Correct 18 ms 1532 KB Output is correct
4 Correct 5 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 384 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 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 8 ms 384 KB Output is correct
16 Correct 18 ms 1532 KB Output is correct
17 Correct 98 ms 8680 KB Output is correct
18 Correct 4 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 4 ms 384 KB Output is correct
21 Correct 4 ms 384 KB Output is correct
22 Incorrect 5 ms 384 KB Output isn't correct
23 Halted 0 ms 0 KB -