oj.uz

Submission #797070

# Submission time Handle Problem Language Result Execution time Memory
797070 2023-07-29T05:55:07 Z vjudge1 Road Construction (JOI21_road_construction) C++17
18 / 100
 384 ms 43852 KB 

// Author : حسن

#include <bits/stdc++.h>



using namespace std;

#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define fi first
#define se second
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"


const int N = 3e5 + 9 , mod = 1e9 + 7;
ll c[N] = {} , dp[N]= {} , a[N] = {}, b[N] = {} , d[N] = {};
vector<ll>v[N] , v1 ,v2;

void solve(){
    ll q , i , j , m , n , z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = 0;
    cin>>n>>k;
    for(i = 1; i <= n; i++){
        cin>>a[i]>>b[i];
    }
    if(k == 1){
        vector<pair<ll,ll>>v1,v2;
        for(i = 1; i <= n; i++){
        v1.pb({a[i] , b[i]});
        v2.pb({b[i] , a[i]});}
        sort(all(v1));
        x = 1e10 ;
        for(auto to : v1){
            if(x <= 1e10)
            mn = min(mn , abs(to.fi - x) + abs(to.se - y));
            x = to.fi;
            y = to.se;
        }
        sort(all(v2));
        x = 1e10;
        for(auto to : v2){
            if(x <= 1e10)
            mn = min(mn , abs(to.fi - x) + abs(to.se - y));
            x = to.fi;
            y = to.se;
        }
        cout<<mn<<"\n";
        return;
    }
    if(n <= 1000){
        vector<ll>v;
        for(i = 1; i <= n; i++)
            for(j = i + 1; j <= n; j++)
                v.pb(abs(a[i] - a[j]) + abs(b[i] - b[j]));
        sort(all(v));
        for(i = 0;i < k; i++)
            cout<<v[i]<<"\n";
        return;
    }/*else if(k <= 10){
    vector<pair<int,int>>v;
    v.pb({a[i] , b[i]});
    sort(all(v));
    mn = -1e9;
    mx = 1e9;
    i = 0;
    set<pair<ll,ll>>st;
    for(auto to : v){
        //v1.pb({to.se , to.se - mn + to.fi - mn});
        //v2.pb(to.se , mx - to.se  + to.fi - mn);
        i++;
    }
    }*/else {
        sort(a + 1, a + n + 1);
        vector<pair<ll,ll>>v;
        multiset<ll>st;
        multiset<pair<ll,ll>>st1 , st2;
        for(i = 2; i <= n; i++)
            v.pb({a[i] - a[i - 1] , i});
        sort(all(v));
        for(i = 0; i < n - 1; i++){
            st.insert(v[i].fi);
            if(v[i].se < n)
                st1.insert({v[i].fi + a[v[i].se + 1] - a[v[i].se] , v[i].se + 1});
        }
        x = max(n , k);
        while(true){
            if(st.size() > x)
                st.erase(--st.end());
            auto it = st1.begin();
            if(st1.size() && it->fi < *(--st.end()) || st.size() < x){
                if(st.size() >= x){
                st.erase(--st.end());
                }
                st.insert(it->fi);
                if(it->se < n && a[it->se + 1])
                st1.insert({it->fi + a[it->se + 1] - a[it->se] , it->se + 1});
                st1.erase(it);
            }else {
            break;
            }
        }
        x = 0;
        for(auto it : st){
            x++;
            if(x <= k)
                cout<<it<<"\n";
        }
    }
}

int main(){

     TL;
     /*
     #ifndef ONLINE_JUDGE
     freopen("input.txt", "r", stdin);
     freopen("output.txt", "w", stdout);
     #endif
     */
int t = 1;
//cin>>t;

while(t--)
     {
     solve();
     }

}
// Author : حسن

Compilation message

road_construction.cpp: In function 'void solve()':
road_construction.cpp:98:26: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   98 |             if(st.size() > x)
      |                ~~~~~~~~~~^~~
road_construction.cpp:101:66: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  101 |             if(st1.size() && it->fi < *(--st.end()) || st.size() < x){
      |                                                        ~~~~~~~~~~^~~
road_construction.cpp:101:27: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  101 |             if(st1.size() && it->fi < *(--st.end()) || st.size() < x){
      |                ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
road_construction.cpp:102:30: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  102 |                 if(st.size() >= x){
      |                    ~~~~~~~~~~^~~~
road_construction.cpp:32:8: warning: unused variable 'q' [-Wunused-variable]
   32 |     ll q , i , j , m , n , z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |        ^
road_construction.cpp:32:20: warning: unused variable 'm' [-Wunused-variable]
   32 |     ll q , i , j , m , n , z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                    ^
road_construction.cpp:32:28: warning: unused variable 'z' [-Wunused-variable]
   32 |     ll q , i , j , m , n , z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                            ^
road_construction.cpp:32:32: warning: unused variable 's' [-Wunused-variable]
   32 |     ll q , i , j , m , n , z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                ^
road_construction.cpp:32:40: warning: unused variable 'f' [-Wunused-variable]
   32 |     ll q , i , j , m , n , z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                        ^
road_construction.cpp:32:43: warning: unused variable 'l' [-Wunused-variable]
   32 |     ll q , i , j , m , n , z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                           ^
road_construction.cpp:32:47: warning: unused variable 'r' [-Wunused-variable]
   32 |     ll q , i , j , m , n , z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                               ^
road_construction.cpp:32:76: warning: unused variable 'mx' [-Wunused-variable]
   32 |     ll q , i , j , m , n , z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                                                            ^~
road_construction.cpp:54:47: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |             mn = min(mn , abs(to.fi - x) + abs(to.se - y));
      |                                            ~~~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 13960 KB Output is correct
2 Correct 56 ms 14000 KB Output is correct
3 Correct 37 ms 12048 KB Output is correct
4 Correct 36 ms 12184 KB Output is correct
5 Correct 55 ms 12908 KB Output is correct
6 Correct 21 ms 11596 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 43820 KB Output is correct
2 Correct 384 ms 43704 KB Output is correct
3 Correct 37 ms 11968 KB Output is correct
4 Correct 306 ms 43520 KB Output is correct
5 Correct 168 ms 43852 KB Output is correct
6 Correct 169 ms 43768 KB Output is correct
7 Correct 214 ms 43164 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 19236 KB Output is correct
2 Correct 93 ms 19240 KB Output is correct
3 Correct 3 ms 7336 KB Output is correct
4 Correct 80 ms 19288 KB Output is correct
5 Correct 97 ms 19240 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 19236 KB Output is correct
2 Correct 93 ms 19240 KB Output is correct
3 Correct 3 ms 7336 KB Output is correct
4 Correct 80 ms 19288 KB Output is correct
5 Correct 97 ms 19240 KB Output is correct
6 Incorrect 363 ms 42552 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 13960 KB Output is correct
2 Correct 56 ms 14000 KB Output is correct
3 Correct 37 ms 12048 KB Output is correct
4 Correct 36 ms 12184 KB Output is correct
5 Correct 55 ms 12908 KB Output is correct
6 Correct 21 ms 11596 KB Output is correct
7 Incorrect 202 ms 29892 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 13960 KB Output is correct
2 Correct 56 ms 14000 KB Output is correct
3 Correct 37 ms 12048 KB Output is correct
4 Correct 36 ms 12184 KB Output is correct
5 Correct 55 ms 12908 KB Output is correct
6 Correct 21 ms 11596 KB Output is correct
7 Correct 363 ms 43820 KB Output is correct
8 Correct 384 ms 43704 KB Output is correct
9 Correct 37 ms 11968 KB Output is correct
10 Correct 306 ms 43520 KB Output is correct
11 Correct 168 ms 43852 KB Output is correct
12 Correct 169 ms 43768 KB Output is correct
13 Correct 214 ms 43164 KB Output is correct
14 Correct 90 ms 19236 KB Output is correct
15 Correct 93 ms 19240 KB Output is correct
16 Correct 3 ms 7336 KB Output is correct
17 Correct 80 ms 19288 KB Output is correct
18 Correct 97 ms 19240 KB Output is correct
19 Incorrect 363 ms 42552 KB Output isn't correct
20 Halted 0 ms 0 KB -