oj.uz

Submission #797068

# Submission time Handle Problem Language Result Execution time Memory
797068 2023-07-29T05:47:51 Z vjudge1 Road Construction (JOI21_road_construction) C++17
11 / 100
 420 ms 43776 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(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:74: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]
   74 |             if(st.size() > x)
      |                ~~~~~~~~~~^~~
road_construction.cpp:77: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]
   77 |             if(st1.size() && it->fi < *(--st.end()) || st.size() < x){
      |                                                        ~~~~~~~~~~^~~
road_construction.cpp:77:27: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   77 |             if(st1.size() && it->fi < *(--st.end()) || st.size() < x){
      |                ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
road_construction.cpp:78: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]
   78 |                 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:59: warning: unused variable 'y' [-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:63: warning: unused variable 'mn' [-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;
      |                                                                            ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 13920 KB Output is correct
2 Correct 58 ms 14020 KB Output is correct
3 Correct 36 ms 12056 KB Output is correct
4 Correct 36 ms 12176 KB Output is correct
5 Correct 53 ms 12868 KB Output is correct
6 Correct 24 ms 11596 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 43756 KB Output is correct
2 Correct 420 ms 43748 KB Output is correct
3 Correct 36 ms 11920 KB Output is correct
4 Correct 308 ms 43500 KB Output is correct
5 Correct 174 ms 43776 KB Output is correct
6 Correct 173 ms 43756 KB Output is correct
7 Correct 208 ms 42992 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 371 ms 42612 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 371 ms 42612 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 13920 KB Output is correct
2 Correct 58 ms 14020 KB Output is correct
3 Correct 36 ms 12056 KB Output is correct
4 Correct 36 ms 12176 KB Output is correct
5 Correct 53 ms 12868 KB Output is correct
6 Correct 24 ms 11596 KB Output is correct
7 Incorrect 207 ms 29952 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 13920 KB Output is correct
2 Correct 58 ms 14020 KB Output is correct
3 Correct 36 ms 12056 KB Output is correct
4 Correct 36 ms 12176 KB Output is correct
5 Correct 53 ms 12868 KB Output is correct
6 Correct 24 ms 11596 KB Output is correct
7 Correct 377 ms 43756 KB Output is correct
8 Correct 420 ms 43748 KB Output is correct
9 Correct 36 ms 11920 KB Output is correct
10 Correct 308 ms 43500 KB Output is correct
11 Correct 174 ms 43776 KB Output is correct
12 Correct 173 ms 43756 KB Output is correct
13 Correct 208 ms 42992 KB Output is correct
14 Incorrect 371 ms 42612 KB Output isn't correct
15 Halted 0 ms 0 KB -