oj.uz

Submission #240411

# Submission time Handle Problem Language Result Execution time Memory
240411 2020-06-19T15:07:30 Z valerikk Strange Device (APIO19_strange_device) C++14
25 / 100
 5000 ms 512932 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 20 ms 1660 KB Output is correct
3 Correct 17 ms 1532 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 384 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 5 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 7 ms 384 KB Output is correct
16 Correct 19 ms 1532 KB Output is correct
17 Correct 91 ms 8680 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 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 4 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 5 ms 384 KB Output is correct
2 Correct 17 ms 768 KB Output is correct
3 Correct 10 ms 512 KB Output is correct
4 Correct 40 ms 640 KB Output is correct
5 Correct 2273 ms 512932 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 1089 ms 175064 KB Output is correct
3 Correct 2578 ms 512436 KB Output is correct
4 Correct 2591 ms 512432 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 1089 ms 175064 KB Output is correct
3 Correct 2578 ms 512436 KB Output is correct
4 Correct 2591 ms 512432 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 3343 ms 447028 KB Output is correct
7 Correct 1275 ms 134652 KB Output is correct
8 Correct 3698 ms 447272 KB Output is correct
9 Correct 3676 ms 447200 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 1089 ms 175064 KB Output is correct
3 Correct 2578 ms 512436 KB Output is correct
4 Correct 2591 ms 512432 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 315 ms 32264 KB Output is correct
7 Correct 495 ms 52000 KB Output is correct
8 Correct 496 ms 52096 KB Output is correct
9 Correct 501 ms 51972 KB Output is correct
10 Correct 1407 ms 26056 KB Output is correct
11 Correct 3749 ms 50464 KB Output is correct
12 Correct 3583 ms 51996 KB Output is correct
13 Correct 2790 ms 56092 KB Output is correct
14 Correct 147 ms 11376 KB Output is correct
15 Execution timed out 5090 ms 31040 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 1008 ms 8672 KB Output is correct
3 Execution timed out 5092 ms 8676 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 20 ms 1660 KB Output is correct
3 Correct 17 ms 1532 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 384 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 5 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 7 ms 384 KB Output is correct
16 Correct 19 ms 1532 KB Output is correct
17 Correct 91 ms 8680 KB Output is correct
18 Correct 5 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 4 ms 384 KB Output isn't correct
23 Halted 0 ms 0 KB -