Submission #1294953

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294953		ender_shayan	Road Construction (JOI21_road_construction)	C++20	6 / 100	10090 ms	75932 KiB

road_construction

#include <bits/stdc++.h>

using namespace std;

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;

typedef long long ll;
typedef long double	ld;
typedef pair<int, int>	pii  ;
typedef pair<ll, ll>	pll  ;
typedef vector<pii>     vii  ;
typedef vector<int>     veci ;
typedef vector<pll>     vll  ;
typedef vector<ll>      vecll;

// find_by_order             order_of_key

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp		        make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl
#define set_dec(x)	    cout << fixed << setprecision(x);
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("in.txt" , "r" , stdin) ; freopen("out.txt" , "w" , stdout);
#define lb              lower_bound
#define ub              upper_bound
#define for1(n)         for(int i=1;i<=n;i++)
#define for0(n)         for(int i=0;i<n;i++)
#define forn(n)         for(int i=n;i>0;i--)
#define pq              priority_queue <int, vector<int>, greater<int>>
const ll mod=4e9+2;
const int N=1<<18;
int n,m,k,o,kk;
vector<int>vecc;
ll d;
pii A[N];
multiset<int> seg[N*2];
multiset<int> segg[N*2];
vector<int>vec;
vector<ll>ans;
void get(int i,ll x,ll y,int l=0,int r=vecc.size(),int v=1){
    for(ll t:seg[v]){
        if(kk==0 || t>d-x-y)break;
        if(o)ans.pb(t+x+y);
        kk--;
    }
    for(ll t:segg[v]){
        if(kk==0 || t>d-x+y)break;
        if(o)ans.pb(t+x+y);
        kk--;
    }
    if(r-l==1)return;
    int mid=(l+r)>>1;
    if(i<mid)get(i,x,y,l,mid,v<<1);
    else get(i,x,y,mid,r,v<<1|1);
}
void upd(int lx,int x,int l=0,int r=vecc.size(),int v=1){
    if(lx>=r)return;
    if(lx<=l){
        seg[v].insert(x);
        while(seg[v].size()>kk){
            auto it=seg[v].end();it--;
            seg[v].erase(it);
        }
        return;
    }
    int mid=(l+r)>>1;
    upd(lx,x,l,mid,v<<1);
    upd(lx,x,mid,r,v<<1|1);
}
void updd(int rx,int x,int l=0,int r=vecc.size(),int v=1){
    if(rx<=l)return;
    if(r<=rx){
        segg[v].insert(x);
        while(segg[v].size()>kk){
            auto it=segg[v].end();it--;
            segg[v].erase(it);
        }
        return;
    }
    int mid=(l+r)>>1;
    updd(rx,x,l,mid,v<<1);
    updd(rx,x,mid,r,v<<1|1);
}
bool check(ll dd){
    d=dd;
    kk=k;
    for1(n){
        get(A[i].S,A[i].F,vecc[A[i].S]);
        upd(A[i].S,-A[i].F-vecc[A[i].S]);
        updd(A[i].S,-A[i].F+vecc[A[i].S]);
    }
    for0(N*2){
        seg[i].clear();
        segg[i].clear();
    }
    return (kk==0);
}
int main(){
    fast_io
    cin>>n>>k;
    for1(n){
        cin>>A[i].F>>A[i].S;
        vecc.pb(A[i].S);
    }
    sort(A+1,A+n+1);
    sort(all(vecc));vecc.resize(unique(all(vecc))-vecc.begin());
    for1(n)A[i].S=lb(all(vecc),A[i].S)-vecc.begin();
    ll l=0,r=mod;
    while(r-l!=1){
        ll mid=(l+r)>>1;
        if(check(mid)==0)l=mid;
        else r=mid;
    }
    o=1;
    check(l);
    sort(all(ans));
    for(ll x:ans)cout<<x<<endl;
    for1(k-ans.size())cout<<l+1<<endl;




}

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