oj.uz

Submission #963072

# Submission time Handle Problem Language Result Execution time Memory
963072 2024-04-14T12:59:03 Z coolboy19521 Garage (IOI09_garage) C++17
100 / 100
 2 ms 2652 KB 
# include <bits/stdc++.h>

namespace ddr {
    # define bpc(bt) __builtin_popcountll(bt)
    # define bcl(bt) __builtin_clz(bt)
    # define alr(v) rbegin(v), end(v)
    # define all(v) begin(v), end(v)
    # define si(v) ((ll)v.size())
    # define mp make_pair
    # define pb push_back
    # define ins insert
    # define se second
    # define fi first

    template <class T, class U> using pi = std::pair <T, U>;
    template <class T> using pq = std::priority_queue <T>;
    template <class T> using mt = std::multiset <T>;
    template <class T> using ve = std::vector <T>;
    template <class T> using qu = std::queue <T>;
    typedef std::string str;
    typedef long long ll;
    typedef bool bo;
    typedef char ch;

    using namespace std;

    const ll inf = 1e18 + 18;
}

using namespace ddr;

const ll sz = 3e5 + 15;

ll n, m, c, i, j;
ll r[sz], w[sz];

int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);

    cin >> n >> m;

    for (i = 1; i <= n; i ++) {
        cin >> r[i];
    }

    for (i = 1; i <= m; i ++) {
        cin >> w[i];
    }

    map <ll, ll> t;
    pq <ll> p;
    qu <ll> q;

    for (i = 1; i <= n; i ++) {
        p.push(-i);
    }

    c = 0;

    for (i = 0; i < 2 * m; i ++) {
        ll a;
        cin >> a;

        if (a > 0) {
            if (!p.empty()) {
                t[a] = p.top();
                p.pop();

                c += w[a] * r[-t[a]];
            } else {
                q.push(a);
            }
        } else {
            p.push(t[-a]);

            if (!q.empty()) {
                ll a = q.front();
                q.pop();

                t[a] = p.top();
                p.pop();

                c += w[a] * r[-t[a]];
            }
        }
    }

    cout << c;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2512 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2392 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2584 KB Output is correct
18 Correct 2 ms 2608 KB Output is correct
19 Correct 2 ms 2652 KB Output is correct
20 Correct 2 ms 2652 KB Output is correct