oj.uz

답안 #946205

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
946205 2024-03-14T12:08:05 Z salmon Road Construction (JOI21_road_construction) C++14
6 / 100
 250 ms 40568 KB 
#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){
                root -> fupdate(v[it1].second,-1);
                it1++;
            }
            while(v[i].first + m >= v[it2].first){
                root -> fupdate(v[it2].second,1);
                it2++;
            }
            num += root -> num - 1;
          if(num >= K * 2) break;
        }
 
        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

road_construction.cpp: In member function 'void node::banana(long long int, long long int)':
road_construction.cpp:84:13: warning: unused variable 'V' [-Wunused-variable]
   84 |         int V = 0;
      |             ^
road_construction.cpp: In function 'int main()':
road_construction.cpp:113:13: warning: unused variable 'Y' [-Wunused-variable]
  113 |         int Y = de[i].second.second;
      |             ^
road_construction.cpp:98:10: 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:10: 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:14: 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:14: 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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 176 ms 22760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 248 ms 40372 KB Output is correct
2 Correct 250 ms 40568 KB Output is correct
3 Correct 160 ms 22616 KB Output is correct
4 Correct 190 ms 39764 KB Output is correct
5 Correct 160 ms 39820 KB Output is correct
6 Correct 165 ms 39716 KB Output is correct
7 Correct 163 ms 39348 KB Output is correct

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 118 ms 34488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 118 ms 34488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 176 ms 22760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 176 ms 22760 KB Output isn't correct
2 Halted 0 ms 0 KB -