Submission #1014527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014527		huutuan	Robots (IOI13_robots)	C++14	76 / 100	559 ms	58120 KiB

robots

#include "robots.h"

#include <bits/stdc++.h>

using namespace std;

const int N=5e4+10, inf=1e9;

struct BIT2d{
   vector<pair<int, int>> t[N];
   int n, m;
   void init(int _n, int _m){
      n=_n, m=_m;
      for (int i=1; i<=n; ++i) t[i].emplace_back(-1, 0);
   }
   void fake_update(int u, int v){
      for (int i=u; i<=n; i+=i&(-i)){
         t[i].emplace_back(v, 0);
      }
   }
   void compress(){
      for (int i=1; i<=n; ++i){
         sort(t[i].begin(), t[i].end());
         t[i].resize(unique(t[i].begin(), t[i].end())-t[i].begin());
      }
   }
   void update(int u, int v, int val){
      for (int i=u; i<=n; i+=i&(-i)){
         for (int j=lower_bound(t[i].begin(), t[i].end(), make_pair(v, -inf))-t[i].begin(); j<(int)t[i].size(); j+=j&(-j)){
            t[i][j].second+=val;
         }
      }
   }
   int get(int u, int v){
      int ans=0;
      for (int i=u; i; i-=i&(-i)){
         for (int j=lower_bound(t[i].begin(), t[i].end(), make_pair(v, inf))-t[i].begin()-1; j; j-=j&(-j)){
            ans+=t[i][j].second;
         }
      }
      return ans;
   }
} bit;

int X[50010], Y[50010];

int sum(int x, int y, int z, int t){
   if (x>z || y>t) return 0;
   return bit.get(z, t)-bit.get(x-1, t)-bit.get(z, y-1)+bit.get(x-1, y-1);
}

int putaway(int A, int B, int T, int _X[], int _Y[], int W[], int S[]) {
   for (int i=0; i<A; ++i) X[i+1]=_X[i]-1;
   for (int i=0; i<B; ++i) Y[i+1]=_Y[i]-1;
   sort(X+1, X+A+1);
   sort(Y+1, Y+B+1);
   vector<int> vx(X+1, X+A+1), vy(Y+1, Y+B+1); vx.push_back(-1); vy.push_back(-1);
   sort(vx.begin(), vx.end()); sort(vy.begin(), vy.end());
   vx.resize(unique(vx.begin(), vx.end())-vx.begin());
   vy.resize(unique(vy.begin(), vy.end())-vy.begin());
   for (int i=1; i<=A; ++i) X[i]=lower_bound(vx.begin(), vx.end(), X[i])-vx.begin();
   for (int i=1; i<=B; ++i) Y[i]=lower_bound(vy.begin(), vy.end(), Y[i])-vy.begin();
   for (int i=0; i<T; ++i){
      W[i]=lower_bound(vx.begin(), vx.end(), W[i])-vx.begin();
      S[i]=lower_bound(vy.begin(), vy.end(), S[i])-vy.begin();
   }
   bit.init((int)vx.size(), (int)vy.size());
   for (int i=0; i<T; ++i) bit.fake_update(W[i], S[i]);
   bit.compress();
   for (int i=0; i<T; ++i) bit.update(W[i], S[i], 1);
   int l=1, r=T;
   while (l<=r){
      int mid=(l+r)>>1;
      bool check=1;
      for (int i=0; i<=A; ++i){
         check&=sum(X[i]+1, Y[0]+1, (int)vx.size(), (int)vy.size())<=(A-i+B-0)*mid;
         check&=sum(X[i]+1, Y[B]+1, (int)vx.size(), (int)vy.size())<=(A-i+B-B)*mid;
      }
      for (int i=0; i<=B; ++i){
         check&=sum(X[0]+1, Y[i]+1, (int)vx.size(), (int)vy.size())<=(A-0+B-i)*mid;
         check&=sum(X[A]+1, Y[i]+1, (int)vx.size(), (int)vy.size())<=(A-A+B-i)*mid;
      }
      if (check) r=mid-1;
      else l=mid+1;
   }
   return l==T+1?-1:l;
}

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