oj.uz

Submission #945882

# Submission time Handle Problem Language Result Execution time Memory
945882 2024-03-14T08:23:23 Z salmon Road Construction (JOI21_road_construction) C++14
5 / 100
 10000 ms 1216168 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];

struct node{

    long long int s, m, e;
    int num;
    node *l,*r;
    set<int> v;

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

        l = NULL;
        r = NULL;
    }

    void update(long long int i, int k, int p){
        if(s == e){
            num += k;
            if(p != -1){
                if(k == 1) v.insert(p);
                else v.erase(p);
            }
            return;
        }

        num += k;

        if(i <= m){
            if(l == NULL) l = new node(s,m);
            l -> update(i,k,p);
        }
        else{
            if(r == NULL) r = new node(m + 1 , e);
            r -> update(i,k,p);
        }
    }

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

        int V = 0;

        if(S <= m){
            if(l == NULL) V += 0;
            else V += l -> query(S,E);
        }
        if(m < E){
            if(r == NULL) V += 0;
            else V += r -> query(S,E);
        }
        return V;
    }

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

        if(s == e){
            if(S == s || e == E) return;

            for(int i : v){
                wacter.push_back(i);
            }
            return;
        }

        int V = 0;

        if(S <= m && l != NULL){
            l -> banana(S,E);
        }
        if(m < E && r != NULL){
            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);

        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(-2.1e9,2.1e9);

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

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

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

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

    int it1 = 0;
    int it2 = 0;

    root = new node(-2e10,2e10);

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

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 27764 KB Output is correct
2 Correct 415 ms 27736 KB Output is correct
3 Correct 396 ms 26568 KB Output is correct
4 Correct 380 ms 26504 KB Output is correct
5 Correct 169 ms 11336 KB Output is correct
6 Correct 16 ms 2652 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10099 ms 1216168 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 10116 ms 413748 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 10116 ms 413748 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 27764 KB Output is correct
2 Correct 415 ms 27736 KB Output is correct
3 Correct 396 ms 26568 KB Output is correct
4 Correct 380 ms 26504 KB Output is correct
5 Correct 169 ms 11336 KB Output is correct
6 Correct 16 ms 2652 KB Output is correct
7 Correct 8518 ms 378224 KB Output is correct
8 Correct 8468 ms 378116 KB Output is correct
9 Correct 370 ms 26508 KB Output is correct
10 Correct 7553 ms 325360 KB Output is correct
11 Correct 5819 ms 297956 KB Output is correct
12 Execution timed out 10064 ms 10688 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 27764 KB Output is correct
2 Correct 415 ms 27736 KB Output is correct
3 Correct 396 ms 26568 KB Output is correct
4 Correct 380 ms 26504 KB Output is correct
5 Correct 169 ms 11336 KB Output is correct
6 Correct 16 ms 2652 KB Output is correct
7 Execution timed out 10099 ms 1216168 KB Time limit exceeded
8 Halted 0 ms 0 KB -