oj.uz

Submission #946000

# Submission time Handle Problem Language Result Execution time Memory
946000 2024-03-14T09:27:12 Z salmon Road Construction (JOI21_road_construction) C++14
5 / 100
 10000 ms 1188316 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);
        }
    }

    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}});
    }

    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;
        }
    }

    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: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

# Verdict Execution time Memory Grader output
1 Correct 232 ms 22740 KB Output is correct
2 Correct 213 ms 22724 KB Output is correct
3 Correct 255 ms 23100 KB Output is correct
4 Correct 212 ms 22948 KB Output is correct
5 Correct 106 ms 8728 KB Output is correct
6 Correct 5 ms 2652 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10061 ms 1188316 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10055 ms 306800 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10055 ms 306800 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 22740 KB Output is correct
2 Correct 213 ms 22724 KB Output is correct
3 Correct 255 ms 23100 KB Output is correct
4 Correct 212 ms 22948 KB Output is correct
5 Correct 106 ms 8728 KB Output is correct
6 Correct 5 ms 2652 KB Output is correct
7 Correct 2873 ms 34660 KB Output is correct
8 Correct 2777 ms 34696 KB Output is correct
9 Correct 219 ms 22980 KB Output is correct
10 Correct 2130 ms 19528 KB Output is correct
11 Correct 1718 ms 18808 KB Output is correct
12 Execution timed out 10039 ms 16376 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 22740 KB Output is correct
2 Correct 213 ms 22724 KB Output is correct
3 Correct 255 ms 23100 KB Output is correct
4 Correct 212 ms 22948 KB Output is correct
5 Correct 106 ms 8728 KB Output is correct
6 Correct 5 ms 2652 KB Output is correct
7 Execution timed out 10061 ms 1188316 KB Time limit exceeded
8 Halted 0 ms 0 KB -