Submission #387890

#	Time	Username	Problem	Language	Result	Execution time	Memory
387890		hackermub	Road Construction (JOI21_road_construction)	C++17	100 / 100	3083 ms	20144 KiB

road_construction

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int,int>
#define float long double
#define pff pair<float,float>
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(),v.end()
#define uid uniform_int_distribution<int>
#define forn(i,st,n,inc) for(int i=st;i<n;i+=inc)
#define rforn(i,st,n,inc) for(int i=st-1;i>=n;i-=inc)
#define bruh cout<<"\nbruh\n"; return 0;
//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pi acos(-1)
const int MOD = 998244353;
const int64_t LLINF = 1e18+7;
const int32_t INF = 1e9+7;


ostream& operator<<(ostream& o,const string& s){
    for(auto c:s) o<<c;
    return o;
}

template<typename F,typename S>
ostream& operator<<(ostream& o,const pair<F,S>& p){
    o<<"["<<p.fi<<","<<p.se<<"]";
    return o;
}

template<typename... T,template<class...> class C>
ostream& operator<<(ostream& o,const C<T...>& v){
    o<<"[";
    int tot=0;
    for(auto x:v){ 
        o<<x;
        if(tot<v.size()-1) o<<",";
        tot++;
    }
    o<<"]";
    return o;
}

vector<string> vec_splitter(string s) {
    s += ',';
    vector<string> res;
    while(!s.empty()) {
        res.push_back(s.substr(0, s.find(',')));
        s = s.substr(s.find(',') + 1);
    }
    return res;
}
void debug_out(
vector<string> __attribute__ ((unused)) args,
__attribute__ ((unused)) int idx, 
__attribute__ ((unused)) int LINE_NUM) { cerr << endl; } 
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
    if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
    stringstream ss; ss << H;
    cerr << args[idx] << " = " << ss.str();
    debug_out(args, idx + 1, LINE_NUM, T...);
}

#ifdef OFFLINE
clock_t Tm=clock();
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...)
#endif

int dist(pii a,pii b){
    return abs(a.fi-b.fi)+abs(a.se-b.se);
}

int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie();
    //If you hack my code , You are gay
    int n,k;
    cin>>n>>k;
    vector<pii> v(n);
    for(int i=0;i<n;i++) cin>>v[i].fi>>v[i].se;
    sort(all(v));
    multiset<int> st;
    int l,r;
    for(int i=1;i<n && k;i++){
        l=i,r=i;
        for(int j=i-1;j>=0 && k;j--){
            r--;
            st.insert(dist(v[i],v[j]));
            k--;
        }
    }
    debug(v);
    debug(st,l,r);
    int last=*--st.end();
    for(int i=l;i<n;i++){
        for(int j=r-1;j>=0;j--){
            if(last<=abs(v[i].fi-v[j].fi)) break;
            if(dist(v[i],v[j])<last){
                debug(j,i,dist(v[i],v[j]));
                st.erase(--st.end());
                st.insert(dist(v[i],v[j]));
                last=*--st.end();
            }
        }
        r=i+1;
    }
    for(auto x:st) cout<<x<<"\n";
    //mara kha
    #ifdef OFFLINE
        cerr<<"Time = "<<(double)(clock()-Tm)/CLOCKS_PER_SEC;
    #endif
    return 0;
}

Compilation message (stderr)

road_construction.cpp: In function 'int32_t main()':
road_construction.cpp:88:9: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
   88 |     int l,r;
      |         ^
road_construction.cpp:88:11: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   88 |     int l,r;
      |           ^

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 27 / 27
• Subtask 6: 35 / 35