Submission #393040

#	Time	Username	Problem	Language	Result	Execution time	Memory
393040		nvmdava	Road Construction (JOI21_road_construction)	C++17	100 / 100	1103 ms	25052 KiB

road_construction

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1000005;
const ll MOD = 1000000007;
const ll INF = 0x3f3f3f3f3f3f3f3f;
 
vector<pair<ll, int> > s, d;
 
ll a[N], b[N];
int loc[N], w[N], rev[N];
int n;
ll k;

int fen[N];

void update(int x, int v){
    while(x <= n){
        fen[x] += v;
        x += x & -x;
    }
}

int query(int x){
    int res = 0;
    while(x){
        res += fen[x];
        x -= x & -x;
    }
    return res;
}
 
vector<ll> ans;
int l1[N], r1[N];
bool count(ll len){
    ll cnt = 0;
    l1[0] = 1;
    r1[0] = 1;
    for(int i = 1; i <= n; ++i){
        l1[i] = l1[i - 1];
        while(a[l1[i]] < a[i] - len)
            ++l1[i];
        r1[i] = r1[i - 1];
        while(r1[i] < n && a[r1[i] + 1] <= a[i] + len)
            ++r1[i];
    }

    int l = 1;
    for(int i = 1; i <= n; ++i){
        while(b[l] < b[i] - len)
            update(w[l++], -1);
        cnt += query(r1[w[i]]) - query(l1[w[i]] - 1);
        if(cnt >= k){
            for(; l < i; ++l)
                update(w[l], -1);
            return 0;
        }

        update(w[i], 1);
    }
    for(; l <= n; ++l)
        update(w[l], -1);
    return 1;
}

void find(ll len){
    set<pair<ll, int> > in;
    int l = 1;
    for(int i = 1; i <= n; ++i){
        while(a[l] < a[i] - len){
            in.erase({b[rev[l]], l});
            ++l;
        }
        auto it = in.lower_bound({b[rev[i]] - len, 0});
        while(it != in.end() && it -> ff <= b[rev[i]] + len){
            ans.push_back(max(abs(b[rev[i]] - it -> ff), abs(a[i] - a[it -> ss])));
            ++it;
        }
        in.insert({b[rev[i]], i});
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin>>n>>k;
 
    for(int x, y, i = 1; i <= n; ++i){
        cin>>x>>y;
        s.push_back({x + y, i});
        d.push_back({x - y, i});
    }
    sort(s.begin(), s.end());
    sort(d.begin(), d.end());
 
    for(int i = 1; i <= n; ++i){
        a[i] = s[i - 1].ff;
        loc[s[i - 1].ss] = i;
    }
    for(int i = 1; i <= n; ++i){
        b[i] = d[i - 1].ff;
        w[i] = loc[d[i - 1].ss];
        rev[w[i]] = i;
    }
    
    ll len = 0;
    for(int i = 31; i >= 0; --i)
        if(count((1LL << i) | len))
            len |= 1LL << i;
    find(len);
    sort(ans.begin(), ans.end());
    ++len;
    while(ans.size() < k)
        ans.push_back(len);
    for(auto& x : ans)
        cout<<x<<'\n';
}

Compilation message (stderr)

road_construction.cpp: In function 'int main()':
road_construction.cpp:118:22: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  118 |     while(ans.size() < k)
      |           ~~~~~~~~~~~^~~

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