oj.uz

Submission #236174

# Submission time Handle Problem Language Result Execution time Memory
236174 2020-05-31T10:50:41 Z nicolaalexandra Garage (IOI09_garage) C++14
100 / 100
 7 ms 384 KB 
#include <bits/stdc++.h>
#define DIM 2010
using namespace std;

int aib[DIM],r[DIM],g[DIM],v[DIM];
int n,m,i,x;
deque <int> d;

void update (int p, int val){
    for (;p<=n;p+=(p&-p))
        aib[p] += val;
}
int query (int p){
    if (p <= 0)
        return 0;
    int sol = 0;
    for (;p;p-=(p&-p))
        sol += aib[p];
    return sol;
}
int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>m;
    for (i=1;i<=n;i++)
        cin>>r[i];
    for (i=1;i<=m;i++)
        cin>>g[i];

    long long sol = 0;
    for (i=1;i<=2*m;i++){
        cin>>x;
        if (x > 0) /// ajunge o noua masina
            d.push_back(x);
        else {
            x = -x;
            update (v[x],-1);
            v[x] = 0; 
        }

        if (d.empty())
            continue;

        if (query(n) == n) /// nu am loc
            continue;

        int st = 1, dr = n, poz = 0;
        while (st <= dr){
            int mid = (st+dr)>>1;
            if (query(mid) < mid){
                poz = mid;
                dr = mid-1;
            } else st = mid+1;
        }

        int idx = d.front();
        d.pop_front();

        sol += 1LL * r[poz] * g[idx];
        v[idx] = poz;

        update (poz,1);

    }
    cout<<sol;

    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 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 5 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 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 7 ms 384 KB Output is correct
15 Correct 6 ms 384 KB Output is correct
16 Correct 6 ms 384 KB Output is correct
17 Correct 6 ms 384 KB Output is correct
18 Correct 7 ms 384 KB Output is correct
19 Correct 7 ms 384 KB Output is correct
20 Correct 7 ms 384 KB Output is correct