Submission #1123578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123578		pera	Road Construction (JOI21_road_construction)	C++17	6 / 100	10085 ms	13220 KiB

road_construction

#include<bits/stdc++.h>
#define LL long long
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]];
   }
   int left;
   multiset<LL> S;
   vector<int> v;
   function<void(int , int , LL , int)> solve = [&](int l , int r , LL C , int g){
      if(l >= r || left <= 0){
         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
      S.insert(-1E16 - 10);
      for(int i : e){
         LL t = x[i] + y[i];
         if(i > m){
            if(!S.empty()){
               auto it = --S.end();
               while(t - *it <= C && left > 0){
                  if(g){
                     v.emplace_back(t - *it);
                  }
                  --left;
                  --it;
               }
            }
         }else{
            S.insert(t);
         }
      }
      S.clear();
      reverse(e.begin() , e.end());
      S.insert(-1E16 - 10);
      for(int i : e){
         LL t = x[i] - y[i];
         if(i > m){
            if(!S.empty()){
               auto it = --S.end();
               while(t - *it <= C && left > 0){
                  if(g){
                     v.emplace_back(t - *it);
                  }
                  --left;
                  --it;
               }
            }
         }else{
            S.insert(t);
         }
      }
      S.clear();
      solve(l , m , C , g);
      solve(m + 1 , r , C , g);
   };
   LL ans = 0;
   for(int bit = 33;bit >= 0;bit --){
      ans += 1LL << bit;
      left = K;
      solve(1 , n , ans , 0);
      if(left <= 0){
         ans -= 1LL << bit;
      }
   }
   left = K;
   solve(1 , n , ans , 1);
   ++ans;
   sort(v.begin() , v.end());
   while(left--){
      v.emplace_back(ans);
   }
   for(int x : v){
      cout << x << '\n';
   }
}

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