Submission #946351

#	Time	Username	Problem	Language	Result	Execution time	Memory
946351		oolimry	Road Construction (JOI21_road_construction)	C++17	0 / 100	10120 ms	1265352 KiB

road_construction

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

int N,K;
vector<pair<long long int,int>> v;
long long int X,Y;
long long int lst[250100];
const long long int inf = 1e18 / 2 * 2;
vector<int> wacter;
long long int plop[250100];
vector<pair<int,pair<int,int>>> de;

struct node{

  int s, m, e;
  int num;
  node *l,*r;

  node(int S, int E){
    s = S;
    e = E;
    m = (s + e)/2;
    num = 0;

    if(s != e){
      l = new node(s,m);
      r = new node(m + 1,e);
    }
  }

  void update(int i, int k){
    if(s == e){
      num += k;
      return;
    }

    num += k;

    if(i <= m){
      l -> update(i,k);
    }
    else{
      r -> update(i,k);
    }
  }

  void fupdate(int i, int k){
    if(s == e){
      num += k;
      return;
    }

    num += k;
  }

  int query(long long int S, long long int E){
    if(S <= lst[s] && lst[e] <= E){
      return num;
    }

    int V = 0;

    if(S <= lst[m]){
      V += l -> query(S,E);
    }
    if(lst[m + 1] <= E){
      V += r -> query(S,E);
    }
    return V;
  }

  void banana(long long int S, long long int E){
    if(S <= lst[s] && lst[e] <= E && s != e){
      if(l -> num > 0) l -> banana(S,E);
      if(r -> num > 0) r -> banana(S,E);
      return;
    }

    if(s == e ){
      if(num > 0) wacter.push_back(s);
      return;
    }

    int V = 0;

    if(S <= lst[m]){
      l -> banana(S,E);
    }
    if(lst[m + 1] <= E){
      r -> banana(S,E);
    }
  }

}*root;

int main(){

  scanf(" %d",&N);
  scanf(" %d",&K);

  for(int i = 0; i < N; i++){
    scanf(" %lld",&X);
    scanf(" %lld",&Y);


    de.push_back({X,{X,Y}});
  }

  sort(de.begin(),de.end());

  for(int i = 0; i < N; i++){
    int X = de[i].second.first;
    int Y = de[i].second.second;

    v.push_back({X,i});
    lst[i] = 0;
    plop[i] = X;
  }

  v.push_back({1e16,-1});

  sort(v.begin(),v.end());

  long long int s = 0;
  long long int e = 5e9;

  root = new node(0,N-1);

  while(s != e){
    long long int m = (s + e)/2;

    int num = 0;
    int it1 = 0;
    int it2 = 0;

    for(int i = 0; i < N; i++){
      while(v[it1].first + m < v[i].first){
        it1++;
      }
      while(v[i].first + m >= v[it2].first){
        it2++;
      }
      num += root -> num - 1;
    }
	assert(it1 <= it2);
    while(it1 != it2){
      root -> fupdate(v[it1].second,-1);
      it1++;
    }

    if(num / 2 >= K){
      e = m;
    }
    else{
      s = m + 1;
    }
  }

  map<long long int,int> mep;

  int it1 = 0;
  int it2 = 0;

  int voom = 0;

  for(int i = 0; i < N; i++){
    while(v[i].first + s > v[it2].first){
      root -> update(v[it2].second,1);
      it2++;
    }
    while(v[it1].first + s <= v[i].first){
      root -> update(v[it1].second,-1);
      it1++;
    }
    root -> banana(lst[v[i].second] - s + 1, lst[v[i].second] + s - 1);

    for(int j : wacter){
      //  if(plop[j] - plop[v[i].second] > s) printf("hh %d %d\n",i,j);
      mep[max(abs(lst[j] - lst[v[i].second]) , abs(plop[j] - plop[v[i].second]) ) ]++;
      voom++;
    }

    wacter.clear();
  }

  voom -= N;

  assert(voom <= K * 2);

  vector<long long int> print;

  mep.erase(0);

  for(pair<long long int, int> ii : mep){
    pair<long long int, int> temp = ii;
    for(; K > 0 && temp.second > 0; K--, temp.second -= 2){
      print.push_back(temp.first);
    }
  }

  while(K > 0){
    print.push_back(s);
    K--;
  }

  for(long long int i : print){
    printf("%lld\n",i);
  }
}
/*
    4 1
    1000000000 1000000000
    -1000000000 -1000000000
    1000000000 -1000000000
    -1000000000 1000000000
    */

Compilation message (stderr)

road_construction.cpp: In member function 'void node::banana(long long int, long long int)':
road_construction.cpp:84:9: warning: unused variable 'V' [-Wunused-variable]
   84 |     int V = 0;
      |         ^
road_construction.cpp: In function 'int main()':
road_construction.cpp:113:9: warning: unused variable 'Y' [-Wunused-variable]
  113 |     int Y = de[i].second.second;
      |         ^
road_construction.cpp:98:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |   scanf(" %d",&N);
      |   ~~~~~^~~~~~~~~~
road_construction.cpp:99:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |   scanf(" %d",&K);
      |   ~~~~~^~~~~~~~~~
road_construction.cpp:102:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |     scanf(" %lld",&X);
      |     ~~~~~^~~~~~~~~~~~
road_construction.cpp:103:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |     scanf(" %lld",&Y);
      |     ~~~~~^~~~~~~~~~~~

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