oj.uz

Submission #946375

# Submission time Handle Problem Language Result Execution time Memory
946375 2024-03-14T14:52:39 Z salmon Road Construction (JOI21_road_construction) C++14
100 / 100
 9394 ms 60532 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;

        long long 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 261 ms 23084 KB Output is correct
2 Correct 217 ms 22716 KB Output is correct
3 Correct 191 ms 22984 KB Output is correct
4 Correct 227 ms 22984 KB Output is correct
5 Correct 103 ms 8716 KB Output is correct
6 Correct 5 ms 2532 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2011 ms 40300 KB Output is correct
2 Correct 2007 ms 40300 KB Output is correct
3 Correct 186 ms 22728 KB Output is correct
4 Correct 1939 ms 39792 KB Output is correct
5 Correct 1816 ms 39792 KB Output is correct
6 Correct 1810 ms 39796 KB Output is correct
7 Correct 1778 ms 39028 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6622 ms 34680 KB Output is correct
2 Correct 6704 ms 39752 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1841 ms 37808 KB Output is correct
5 Correct 5711 ms 40008 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6622 ms 34680 KB Output is correct
2 Correct 6704 ms 39752 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1841 ms 37808 KB Output is correct
5 Correct 5711 ms 40008 KB Output is correct
6 Correct 7130 ms 39748 KB Output is correct
7 Correct 7146 ms 39752 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 6925 ms 39756 KB Output is correct
11 Correct 1802 ms 37812 KB Output is correct
12 Correct 5441 ms 39996 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 23084 KB Output is correct
2 Correct 217 ms 22716 KB Output is correct
3 Correct 191 ms 22984 KB Output is correct
4 Correct 227 ms 22984 KB Output is correct
5 Correct 103 ms 8716 KB Output is correct
6 Correct 5 ms 2532 KB Output is correct
7 Correct 2657 ms 36664 KB Output is correct
8 Correct 2576 ms 36928 KB Output is correct
9 Correct 194 ms 23008 KB Output is correct
10 Correct 2057 ms 21564 KB Output is correct
11 Correct 1631 ms 20536 KB Output is correct
12 Correct 1382 ms 21284 KB Output is correct
13 Correct 1441 ms 20408 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 23084 KB Output is correct
2 Correct 217 ms 22716 KB Output is correct
3 Correct 191 ms 22984 KB Output is correct
4 Correct 227 ms 22984 KB Output is correct
5 Correct 103 ms 8716 KB Output is correct
6 Correct 5 ms 2532 KB Output is correct
7 Correct 2011 ms 40300 KB Output is correct
8 Correct 2007 ms 40300 KB Output is correct
9 Correct 186 ms 22728 KB Output is correct
10 Correct 1939 ms 39792 KB Output is correct
11 Correct 1816 ms 39792 KB Output is correct
12 Correct 1810 ms 39796 KB Output is correct
13 Correct 1778 ms 39028 KB Output is correct
14 Correct 6622 ms 34680 KB Output is correct
15 Correct 6704 ms 39752 KB Output is correct
16 Correct 1 ms 2392 KB Output is correct
17 Correct 1841 ms 37808 KB Output is correct
18 Correct 5711 ms 40008 KB Output is correct
19 Correct 7130 ms 39748 KB Output is correct
20 Correct 7146 ms 39752 KB Output is correct
21 Correct 1 ms 2396 KB Output is correct
22 Correct 1 ms 2396 KB Output is correct
23 Correct 6925 ms 39756 KB Output is correct
24 Correct 1802 ms 37812 KB Output is correct
25 Correct 5441 ms 39996 KB Output is correct
26 Correct 2657 ms 36664 KB Output is correct
27 Correct 2576 ms 36928 KB Output is correct
28 Correct 194 ms 23008 KB Output is correct
29 Correct 2057 ms 21564 KB Output is correct
30 Correct 1631 ms 20536 KB Output is correct
31 Correct 1382 ms 21284 KB Output is correct
32 Correct 1441 ms 20408 KB Output is correct
33 Correct 8429 ms 60532 KB Output is correct
34 Correct 9394 ms 60464 KB Output is correct
35 Correct 7427 ms 45688 KB Output is correct
36 Correct 4728 ms 45428 KB Output is correct
37 Correct 4702 ms 45428 KB Output is correct
38 Correct 5201 ms 44156 KB Output is correct