Submission #1123438

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123438		pera	Road Construction (JOI21_road_construction)	C++17	0 / 100	10091 ms	2102004 KiB

road_construction

#include<bits/stdc++.h>
using namespace std;
int main(){
   cin.tie(0)->sync_with_stdio(0);
   int n , K;
   cin >> n >> K;
   vector<int> x(n + 1) , y(n + 1);
   for(int i = 1;i <= n;i ++){
      cin >> x[i] >> y[i];
   }
   auto nx = x , ny = y;
   vector<int> o(n + 1);
   iota(o.begin() , o.end() , 0);
   sort(o.begin() + 1 , o.end() , [&](int i , int j){
      return pair<int , int>{x[i] , y[i]} < pair<int , int>{x[j] , y[j]};
   });
   for(int i = 1;i <= n;i ++){
      x[i] = nx[o[i]];
      y[i] = ny[o[i]];
   }
   vector<int> f(2 * n + 1);
   auto upd = [&](int x , int w){
      while(x <= 2 * n){
         f[x] += w;
         x += x&-x;
      }
   };
   auto query = [&](int x){
      int s = 0;
      while(x > 0){
         s += f[x];
         x -= x&-x;
      }
      return s;
   };
   function<int(int , int , int)> solve = [&](int l , int r , int C){
      if(l >= r){
         return 0;
      }
      int m = (l + r) / 2;
      vector<int> e(r - l + 1);
      iota(e.begin() , e.end() , l);
      sort(e.begin() , e.end() , [&](int i , int j){
         return pair<int , int>{y[i] , x[i]} < pair<int , int>{y[j] , x[j]};
      });
      //(x[i] + y[i]) - (x[j] + y[j]) <= C
      //(x[i] - y[i]) - (x[j] - y[j]) <= C
      vector<int> values;
      for(int i = l;i <= r;i ++){
         int t = x[i] + y[i];
         values.emplace_back(t);
         values.emplace_back(t - C);
      }
      sort(values.begin() , values.end());
      map<int , int> M;
      for(int i = 0;i < (int)values.size();i ++){
         M[values[i]] = (i > 0 ? M[values[i - 1]] + (values[i] != values[i - 1]) : 1);
      }
      int cnt = 0;
      for(int i : e){
         int t = x[i] + y[i];
         if(i > m){
            cnt += query(2 * n) - query(M[t - C] - 1);
         }else{
            upd(M[t] , +1);
         }
      }
      for(int i = l;i <= m;i ++){
         upd(M[x[i] + y[i]] , -1);
      }
      M.clear();
      vector<int>().swap(values);
      for(int i = l;i <= r;i ++){
         int t = x[i] - y[i];
         values.emplace_back(t);
         values.emplace_back(t - C);
      }
      sort(values.begin() , values.end());
      for(int i = 0;i < (int)values.size();i ++){
         M[values[i]] = (i > 0 ? M[values[i - 1]] + (values[i] != values[i - 1]) : 1);
      }
      reverse(e.begin() , e.end());
      for(int i : e){
         int t = x[i] - y[i];
         if(i > m){
            cnt += query(2 * n) - query(M[t - C] - 1);
         }else{
            upd(M[t] , +1);
         }
      }
      for(int i = l;i <= m;i ++){
         upd(M[x[i] - y[i]] , -1);
      }
      return cnt + solve(l , m , C) + solve(m + 1 , r , C);
   };
   int ans = 0;
   for(int bit = 24;bit >= 0;bit --){
      ans += 1 << bit;
      int cnt = solve(1 , n , ans);
      if(cnt >= K){
         ans -= 1 << bit;
      }
   }
   vector<int> v;
   //!
   function<void(int , int)> solve_dists = [&](int l , int r){
      if(l >= r){
         return;
      }
      int m = (l + r) / 2;
      vector<int> e(r - l + 1);
      iota(e.begin() , e.end() , l);
      sort(e.begin() , e.end() , [&](int i , int j){
         return pair<int , int>{y[i] , x[i]} < pair<int , int>{y[j] , x[j]};
      });
      //(x[i] + y[i]) - (x[j] + y[j]) <= C
      //(x[i] - y[i]) - (x[j] - y[j]) <= C
      multiset<int> S;
      S.insert(-2E9 - 10);
      for(int i : e){
         int t = x[i] + y[i];
         if(i > m){
            if(!S.empty()){
               auto it = --S.end();
               while(t - *it <= ans){
                  v.emplace_back(t - *it);
                  --it;
               }
            }
         }else{
            S.insert(t);
         }
      }
      S.clear();
      reverse(e.begin() , e.end());
      S.insert(-2E9 - 10);
      for(int i : e){
         int t = x[i] - y[i];
         if(i > m){
            if(!S.empty()){
               auto it = --S.end();
               while(t - *it <= ans){
                  v.emplace_back(t - *it);
                  --it;
               }
            }
         }else{
            S.insert(t);
         }
      }
      solve_dists(l , m);
      solve_dists(m + 1 , r);
   };
   solve_dists(1 , n);
   ++ans;
   sort(v.begin() , v.end());
   while((int)v.size() < K){
      v.emplace_back(ans);
   }
   for(int x : v){
      cout << x << " ";
   }
   cout << '\n';
}
/*
10 10
10 -8
7 2
7 -8
-3 -6
-2 1
-8 6
8 -1
2 4
6 -6
2 -1
*/

• Subtask 1: 0 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 20
• Subtask 5: 0 / 27
• Subtask 6: 0 / 35