제출 #392951

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
392951		nvmdava	Road Construction (JOI21_road_construction)	C++17	65 / 100	10069 ms	77792 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];

vector<int> seg[N];

void build(int id, int l, int r){
    if(l == r){
        seg[id].push_back({w[l]});
        return;
    }
    int m = (l + r) >> 1;
    build(id << 1, l, m);
    build(id << 1 | 1, m + 1, r);
    int i1 = 0;
    int i2 = 0;
    while(i1 < seg[id << 1].size() && i2 < seg[id << 1 | 1].size()){
        if(seg[id << 1][i1] < seg[id << 1 | 1][i2])
            seg[id].push_back(seg[id << 1][i1++]);
        else
            seg[id].push_back(seg[id << 1 | 1][i2++]);
    }
    while(i1 < seg[id << 1].size())
        seg[id].push_back(seg[id << 1][i1++]);
    while(i2 < seg[id << 1 | 1].size())
        seg[id].push_back(seg[id << 1 | 1][i2++]);
}
int n;
ll k;
vector<ll> ans;
int query(int id, int l, int r, int L, int R, int le, int ri, int x){
    if(l > R || r < L) return 0;
    if(L <= l && r <= R){
        le = lower_bound(seg[id].begin(), seg[id].end(), le) - seg[id].begin();
        ri = upper_bound(seg[id].begin(), seg[id].end(), ri) - seg[id].begin() - 1;
        if(x)
            for(int i = le; i <= ri; ++i)
                ans.push_back(max(abs(a[x] - a[seg[id][i]]), abs(b[rev[x]] - b[rev[seg[id][i]]])));
        return ri - le + 1;
    }
    int m = (l + r) >> 1;
    return query(id << 1, l, m, L, R, le, ri, x) + query(id << 1 | 1, m + 1, r, L, R, le, ri, x);
}

bool count(ll len, bool get){
    ll cnt = 0;
    for(int i = 1; i <= n; ++i){
        int l1 = lower_bound(a + 1, a + i, a[i] - len) - a;
        int r1 = i - 1;
        int l2 = lower_bound(b + 1, b + rev[i], b[rev[i]] - len) - b;
        int r2 = upper_bound(b + rev[i], b + n + 1, b[rev[i]] + len) - b - 1;
        if(l1 > r1 || l2 > r2) continue;
        cnt += query(1, 1, n, l2, r2, l1, r1, get * i);
        if(cnt >= k) return 0;
    }
    return 1;
}

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;
    }
    build(1, 1, n);
    ll len = 0;
    for(int i = 32; i >= 0; --i)
        if(count((1LL << i) | len, 0))
            len |= 1LL << i;
    count(len, 1);
    sort(ans.begin(), ans.end());
    ++len;
    while(ans.size() < k)
        ans.push_back(len);
    for(auto& x : ans)
        cout<<x<<'\n';
}

컴파일 시 표준 에러 (stderr) 메시지

road_construction.cpp: In function 'void build(int, int, int)':
road_construction.cpp:28:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     while(i1 < seg[id << 1].size() && i2 < seg[id << 1 | 1].size()){
      |           ~~~^~~~~~~~~~~~~~~~~~~~~
road_construction.cpp:28:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     while(i1 < seg[id << 1].size() && i2 < seg[id << 1 | 1].size()){
      |                                       ~~~^~~~~~~~~~~~~~~~~~~~~~~~~
road_construction.cpp:34:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     while(i1 < seg[id << 1].size())
      |           ~~~^~~~~~~~~~~~~~~~~~~~~
road_construction.cpp:36:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     while(i2 < seg[id << 1 | 1].size())
      |           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:102: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]
  102 |     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: 0 / 35