Submission #797082

#	Time	Username	Problem	Language	Result	Execution time	Memory
797082		vjudge1	Road Construction (JOI21_road_construction)	C++17	18 / 100	2343 ms	327556 KiB

road_construction

// 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 <= 10){
        vector<pair<ll,pair<ll,ll>>>v1,v2;
        for(i = 1; i <= n; i++){
        v1.pb({a[i] , {b[i] , i}});
        v2.pb({b[i] , {a[i] , i}});}
        sort(all(v1));
        x = 1e10 ;
        set<pair<int,int>>st;
        for(i = 0; i < v1.size(); i++){
            x = max(i - k , 0ll);
            for(j = i - 1;  j >= x; j--){
                   st.insert({v1[i].se.se , v1[j].se.se});
            }
        }
        /*for(auto to : v1){
            mn = min(mn , abs(to.fi - x) + abs(to.se - y));
            x = to.fi;
            y = to.se;
        }*/
        sort(all(v2));
        x = 1e10;
        for(i = 0; i < v2.size(); i++){
            x = max(i - k , 0ll);
            for(j = i - 1;  j >= x; j--){
                   st.insert({v2[i].se.se , v2[j].se.se});
            }
        }
        vector<ll>v;
        for(auto it : st){
            v.pb(abs(a[it.fi] - a[it.se]) + abs(b[it.fi] - b[it.se]));
        }sort(all(v));
        for(i = 0; i < k; i++)
            cout<<v[i]<<"\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 (stderr)

road_construction.cpp: In function 'void solve()':
road_construction.cpp:45:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for(i = 0; i < v1.size(); i++){
      |                    ~~^~~~~~~~~~~
road_construction.cpp:58:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for(i = 0; i < v2.size(); i++){
      |                    ~~^~~~~~~~~~~
road_construction.cpp:109: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]
  109 |             if(st.size() > x)
      |                ~~~~~~~~~~^~~
road_construction.cpp:112: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]
  112 |             if(st1.size() && it->fi < *(--st.end()) || st.size() < x){
      |                                                        ~~~~~~~~~~^~~
road_construction.cpp:112:27: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  112 |             if(st1.size() && it->fi < *(--st.end()) || st.size() < x){
      |                ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
road_construction.cpp:113: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]
  113 |                 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 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 0 / 20
• Subtask 5: 0 / 27
• Subtask 6: 0 / 35