Submission #1264229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264229		DeltaStruct	Robots (IOI13_robots)	C++20	90 / 100	1248 ms	12456 KiB

robots

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

int putaway(int x,int y,int n,int A[],int B[],int c[],int d[]){
  vector<pair<int,int>> C; for (int i(0);i < n;++i) C.emplace_back(c[i],d[i]);
  sort(A,A+x),sort(B,B+y),sort(C.begin(),C.end());
  int l = n+1,r = -1,mid;
  while(abs(l-r)>1){
    mid = (l+r)/2;
    priority_queue<int> M;
    for (int i(0),k(0);i < x;++i){
      for (;k < n&&C[k].first<A[i];++k) M.emplace(C[k].second);
      for (int j(0);j < mid&&!M.empty();++j) M.pop();
    }
    priority_queue<int,vector<int>,greater<int>> T; while(!M.empty()) T.emplace(M.top()),M.pop();
    for (int i(0);i < n;++i) if (A[x-1]<=C[i].first) T.emplace(C[i].second);
    for (int i(0);i < y;++i) for (int k(0);k < mid&&!T.empty()&&T.top()<B[i];++k) T.pop();
    if (T.empty()) l = mid;
    else r = mid;
  }
  return (l==n+1?-1:l);
}

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