oj.uz

Submission #797082

# Submission time Handle Problem Language Result Execution time Memory
797082 2023-07-29T06:15:00 Z vjudge1 Road Construction (JOI21_road_construction) C++17
18 / 100
 2343 ms 327556 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 <= 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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 14028 KB Output is correct
2 Correct 56 ms 14004 KB Output is correct
3 Correct 36 ms 12108 KB Output is correct
4 Correct 36 ms 12152 KB Output is correct
5 Correct 53 ms 12864 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 366 ms 43772 KB Output is correct
2 Correct 382 ms 43772 KB Output is correct
3 Correct 37 ms 11924 KB Output is correct
4 Correct 301 ms 43612 KB Output is correct
5 Correct 178 ms 43864 KB Output is correct
6 Correct 172 ms 43744 KB Output is correct
7 Correct 224 ms 43032 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 54460 KB Output is correct
2 Correct 420 ms 54532 KB Output is correct
3 Correct 3 ms 7380 KB Output is correct
4 Correct 249 ms 38760 KB Output is correct
5 Correct 390 ms 54508 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 54460 KB Output is correct
2 Correct 420 ms 54532 KB Output is correct
3 Correct 3 ms 7380 KB Output is correct
4 Correct 249 ms 38760 KB Output is correct
5 Correct 390 ms 54508 KB Output is correct
6 Incorrect 2343 ms 327556 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 14028 KB Output is correct
2 Correct 56 ms 14004 KB Output is correct
3 Correct 36 ms 12108 KB Output is correct
4 Correct 36 ms 12152 KB Output is correct
5 Correct 53 ms 12864 KB Output is correct
6 Correct 21 ms 11596 KB Output is correct
7 Incorrect 195 ms 29860 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 14028 KB Output is correct
2 Correct 56 ms 14004 KB Output is correct
3 Correct 36 ms 12108 KB Output is correct
4 Correct 36 ms 12152 KB Output is correct
5 Correct 53 ms 12864 KB Output is correct
6 Correct 21 ms 11596 KB Output is correct
7 Correct 366 ms 43772 KB Output is correct
8 Correct 382 ms 43772 KB Output is correct
9 Correct 37 ms 11924 KB Output is correct
10 Correct 301 ms 43612 KB Output is correct
11 Correct 178 ms 43864 KB Output is correct
12 Correct 172 ms 43744 KB Output is correct
13 Correct 224 ms 43032 KB Output is correct
14 Correct 438 ms 54460 KB Output is correct
15 Correct 420 ms 54532 KB Output is correct
16 Correct 3 ms 7380 KB Output is correct
17 Correct 249 ms 38760 KB Output is correct
18 Correct 390 ms 54508 KB Output is correct
19 Incorrect 2343 ms 327556 KB Output isn't correct
20 Halted 0 ms 0 KB -