Submission #236174

#	Time	Username	Problem	Language	Result	Execution time	Memory
236174		nicolaalexandra	Garage (IOI09_garage)	C++14	100 / 100	7 ms	384 KiB

garage

#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 / 100