Submission #1199699

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199699		Hamed_Ghaffari	Robots (IOI13_robots)	C++20	100 / 100	797 ms	18632 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;

#define ff first
#define ss second

const int MXN = 1e6+5;

int px[MXN], py[MXN], cnt[MXN], ox[MXN];

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    sort(X, X+A);
    sort(Y, Y+B);
    for(int i=0; i<T; i++) {
        if((A==0 || W[i]>=X[A-1]) && (B==0 || S[i]>=Y[B-1])) return -1;
        px[i] = upper_bound(X, X+A, W[i])-X;
        py[i] = upper_bound(Y, Y+B, S[i])-Y;
    }
    iota(ox, ox+T, 0);
    sort(ox, ox+T, [&](int i, int j) {
        return px[i] < px[j];
    });
    int l=0, r=T, mid;
    while(r-l>1) {
        mid = l+r>>1;
        
        priority_queue<pii> pq;
        int ptr = 0;
        for(int i=0; i<=A; i++) {
            while(ptr<T && px[ox[ptr]]==i) {
                pq.push({py[ox[ptr]], ox[ptr]});
                ptr++;
            }
            if(i<A) for(int c=0; c<mid && !pq.empty(); c++)
                pq.pop();
        }

        int wh = B;
        ll sum = 0;
        while(!pq.empty()) {
            int p = pq.top().ff;
            if(p==B) break;
            if(wh>p) {
                sum += 1ll*(wh-p)*mid;
                wh = p;
            }
            if(!sum) break;
            sum--;
            pq.pop();
        }
        (pq.empty() ? r : l) = mid;
    }
    return r;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37
• Subtask 5: 10 / 10