oj.uz

답안 #945943

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
945943 2024-03-14T08:58:23 Z salmon Road Construction (JOI21_road_construction) C++14
5 / 100
 10000 ms 1155960 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{

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

    node(long long int S, long long 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(long long int i, int k){
        if(s == e){
            num += k;
            return;
        }

        num += k;

        if(i <= m){
            l -> update(i,k);
        }
        else{
            r -> update(i,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+Y,{X,Y}});
        lst[i] = X + Y;
        plop[i] = 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 - Y,i});
        lst[i] = X + Y;
        plop[i] = X - Y;
    }

    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 -> update(v[it1].second,-1);
                it1++;
            }
            while(v[i].first + m >= v[it2].first){
                root -> update(v[it2].second,1);
                it2++;
            }
            num += root -> query(lst[v[i].second] - m, lst[v[i].second] + m ) - 1;
        }

        while(it1 != it2){
            root -> update(v[it1].second,-1);
            it1++;
        }

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

//printf("%lld ",s);
    map<long long int,int> mep;

    int it1 = 0;
    int it2 = 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]) ) ]++;
        }

        wacter.clear();
    }

    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 5
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:75:13: warning: unused variable 'V' [-Wunused-variable]
   75 |         int V = 0;
      |             ^
road_construction.cpp: In function 'int main()':
road_construction.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
road_construction.cpp:90:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |     scanf(" %d",&K);
      |     ~~~~~^~~~~~~~~~
road_construction.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |         scanf(" %lld",&X);
      |         ~~~~~^~~~~~~~~~~~
road_construction.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         scanf(" %lld",&Y);
      |         ~~~~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 183 ms 22720 KB Output is correct
2 Correct 195 ms 22980 KB Output is correct
3 Correct 196 ms 22772 KB Output is correct
4 Correct 181 ms 23016 KB Output is correct
5 Correct 118 ms 8796 KB Output is correct
6 Correct 7 ms 2652 KB Output is correct

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10149 ms 1155960 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10022 ms 307212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10022 ms 307212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 183 ms 22720 KB Output is correct
2 Correct 195 ms 22980 KB Output is correct
3 Correct 196 ms 22772 KB Output is correct
4 Correct 181 ms 23016 KB Output is correct
5 Correct 118 ms 8796 KB Output is correct
6 Correct 7 ms 2652 KB Output is correct
7 Correct 2760 ms 39788 KB Output is correct
8 Correct 2987 ms 37880 KB Output is correct
9 Correct 198 ms 22868 KB Output is correct
10 Correct 2304 ms 22668 KB Output is correct
11 Correct 1971 ms 21632 KB Output is correct
12 Execution timed out 10060 ms 19260 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 183 ms 22720 KB Output is correct
2 Correct 195 ms 22980 KB Output is correct
3 Correct 196 ms 22772 KB Output is correct
4 Correct 181 ms 23016 KB Output is correct
5 Correct 118 ms 8796 KB Output is correct
6 Correct 7 ms 2652 KB Output is correct
7 Execution timed out 10149 ms 1155960 KB Time limit exceeded
8 Halted 0 ms 0 KB -