Submission #1208768

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208768		pera	Robots (IOI13_robots)	C++20	76 / 100	3095 ms	12188 KiB

robots

#include<bits/stdc++.h>
#include "robots.h"
using namespace std;
const int N = 50000;
int t[4 * N] , lz[4 * N];
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
   sort(X , X + A);
   sort(Y , Y + B);
   auto igA = [&](int x){
      int p = -1;
      for(int bit = 17;bit >= 0;bit --){
         p += 1 << bit;
         if(p >= A){
            p -= 1 << bit;
         }else if(X[p] > x){
            p -= 1 << bit;
         }
      }
      ++p;
      return A - p;
   };
   auto igB = [&](int x){
      int p = -1;
      for(int bit = 17;bit >= 0;bit --){
         p += 1 << bit;
         if(p >= B){
            p -= 1 << bit;
         }else if(Y[p] > x){
            p -= 1 << bit;
         }
      }
      ++p;
      return B - p;
   };
   vector<int> cA(T) , cB(T);
   for(int i = 0;i < T;i ++){
      cA[i] = igA(W[i]);
      cB[i] = igB(S[i]);
      if(cA[i] + cB[i] == 0){
         return -1;
      }
   }
   vector<int> oy(T);
   iota(oy.begin() , oy.end() , 0);
   sort(oy.begin() , oy.end() , [&](int i , int j){
      return pair<int , int>{cB[i] , -cA[i]} < pair<int , int>{cB[j] , -cA[j]};
   });
   reverse(oy.begin() , oy.end());
   auto solveB = [&](vector<int> v){
      vector<int> c(B + 1);
      for(int x : v){
         c[x]++;
      }
      int ans = 0;
      for(int i = 1;i <= B;i ++){
         c[i] += c[i - 1];
         ans = max(ans , (c[i] + i - 1) / i);
      }
      return ans;
   };
   vector<int> t(4 * A) , lz(4 * A);
   auto push = [&](int u){
      t[u * 2] += lz[u];
      t[u * 2 + 1] += lz[u];
      lz[u * 2] += lz[u];
      lz[u * 2 + 1] += lz[u];
      lz[u] = 0;
   };
   function<void(int , int , int , int , int , int)> update = [&](int u , int l , int r , int L , int R , int x){
      if(l > r || r < L || l > R){
         return;
      }
      if(L <= l && r <= R){
         t[u] += x;
         lz[u] += x;
         return;
      }
      int m = (l + r) / 2;
      push(u);
      update(u * 2 , l , m , L , R , x);
      update(u * 2 + 1 , m + 1 , r , L , R , x);
      t[u] = min(t[u * 2] , t[u * 2 + 1]);
   };
   function<int(int , int , int , int , int)> query = [&](int u , int l , int r , int L , int R){
      if(l > r || r < L || l > R){
         return (int)1E9;
      }
      if(L <= l && r <= R){
         return t[u];
      }
      int m = (l + r) / 2;
      push(u);
      return min(query(u * 2 , l , m , L , R) , query(u * 2 + 1 , m + 1 , r , L , R));
   };
   function<void(int , int , int , int)> build = [&](int u , int l , int r , int v){
      if(l > r){
         return;
      }
      lz[u] = 0;
      if(l == r){
         t[u] = min(1000000LL , 1LL * r * v);
         return;
      }
      int m = (l + r) / 2;
      build(u * 2 , l , m , v);
      build(u * 2 + 1 , m + 1 , r , v);
      t[u] = min(t[u * 2] , t[u * 2 + 1]);
   };
   auto pos = [&](int v){
      vector<int> pref(A + 1) , left;
      for(int i = 1;i <= A;i ++){
         pref[i] = min(1000000LL , 1LL * i * v);
      }
      build(1 , 1 , A , v);
      auto can_insert = [&](int x){
         return (query(1 , 1 , A , x , A) > 0);
      };
      auto insert = [&](int x){
         update(1 , 1 , A , x , A , -1);
      };
      for(int i = 0;i < T;i ++){
         if(!cA[i]){
            left.emplace_back(cB[i]);
         }else if(!cB[i]){
            if(!can_insert(cA[i])){
               return false;
            }
            insert(cA[i]);
         }
      }
      for(int i = T - 1;i >= 0;i --){
         int j = oy[i];
         if(!cA[j] || !cB[j]){
            continue;
         }
         if(can_insert(cA[j])){
            insert(cA[j]);
         }else{
            left.emplace_back(cB[j]);
         }
      }
      return solveB(left) <= v;
   };
   int ans = 0;
   for(int bit = 20;bit >= 0;bit --){
      ans += 1 << bit;
      if(pos(ans) == true){
         ans -= 1 << bit;
      }
   }
   ++ans;
   return ans;
}

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