oj.uz

답안 #1112092

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1112092 2024-11-13T16:22:25 Z onbert Road Construction (JOI21_road_construction) C++17
13 / 100
 4732 ms 17244 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 250005, INF = 4e9 + 10;
int n, k;
pair<int, int> a[maxn];
int ysz;
vector<int> xvals = {-INF}, yvals = {-INF};
int ldc(int x) {return lower_bound(yvals.begin(), yvals.end(), x) - yvals.begin();}
int rdc(int x) {return upper_bound(yvals.begin(), yvals.end(), x) - yvals.begin() - 1;}

int fen[maxn];
void update(int id) {
    while (id <= ysz) {
        fen[id]++;
        id += (id & -id);
    } 
}
int qry(int id) {
    int val = 0;
    while (id >= 1) {
        val += fen[id];
        id -= (id & -id);
    }
    return val;
}

int cunt(int dist) {
    int ans = 0, pt = 0;
    for (int i=1;i<=n;i++) {
        while (pt+1 <= n && a[pt+1].first <= a[i].first + dist) {
            pt++;
            int L = ldc(a[pt].second - dist), R = rdc(a[pt].second + dist);
            ans -= qry(R) - qry(L-1);
            // cout << "- " << (a[pt].first+a[pt].second)/2 << " " << (a[pt].first-a[pt].second)/2 << " " << qry(R) - qry(L-1) << endl;
        }
        int L = ldc(a[i].second - dist), R = rdc(a[i].second + dist);
        ans += qry(R) - qry(L-1);
        // cout << "+ " << (a[i].first+a[i].second)/2 << " " << (a[i].first-a[i].second)/2 << " " << qry(R) - qry(L-1) << endl;
        int pos = ldc(a[i].second);
        update(pos);
    }
    return ans;
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    for (int i=1;i<=n;i++) {
        int x, y;
        cin >> x >> y;
        a[i] = {x+y, x-y};
        xvals.push_back(x+y);
        yvals.push_back(x-y);
    }
    sort(a+1, a+n+1);
    sort(xvals.begin(), xvals.end());
    xvals.erase(unique(xvals.begin(), xvals.end()), xvals.end());
    sort(yvals.begin(), yvals.end());
    yvals.erase(unique(yvals.begin(), yvals.end()), yvals.end());
    ysz = yvals.size() - 1;

    int L = 1, R = INF;
    while (L < R) {
        int mid = (L+R)/2;
        if (cunt(mid) < k) L = mid+1;
        else R = mid;
    }
    
    int dist = L - 1;
    vector<int> ans;
    multiset<pair<int,int>> s;
    s.insert({INF, INF});
    int l = 0, r = 0;
    int cnt = 0;
    for (int i=1;i<=n;i++) {
        while (r+1 <= n && a[r+1].first <= a[i].first + dist) {
            r++;
            s.insert({a[r].second, a[r].first});
        }
        while (l+1 <= n && a[l+1].first < a[i].first - dist) {
            l++;
            s.erase({a[l].second, a[l].first});
        }
        // cout << "test\n";
        // cout << (a[i].first+a[i].second)/2 << " " << (a[i].first-a[i].second)/2 << endl;

        // auto it = s.lower_bound({a[i].second - dist, -INF});
        // while ((it->first) <= a[i].second + dist) {
        //     pair<int,int> cur = *it;
        //     if (a[i].first!=cur.second || a[i].second!=cur.first) {
        //         ans.push_back(max(abs(a[i].first - cur.second), abs(a[i].second - cur.first)));
        //         // assert(max(abs(a[i].first - cur.second), abs(a[i].second - cur.first)) <= dist);
        //         cnt++;
        //         // cout << max(abs(a[i].first - cur.second), abs(a[i].second - cur.first)) << endl;
        //     }
        //     it++;
        // }
        for (auto [x, y]:s) {
            if ((a[i].second!=x || a[i].first!=y) && abs(a[i].second - x) <= dist) {
                ans.push_back(max(abs(a[i].first - y), abs(a[i].second - x)));
            }
        }
    }
    while (ans.size() < 2*k) ans.push_back(L);
    sort(ans.begin(), ans.end());
    for (int i=0;i<2*k;i+=2) cout << ans[i] << '\n';
}

Compilation message

road_construction.cpp: In function 'int main()':
road_construction.cpp:105:23: 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]
  105 |     while (ans.size() < 2*k) ans.push_back(L);
      |            ~~~~~~~~~~~^~~~~
road_construction.cpp:75:9: warning: unused variable 'cnt' [-Wunused-variable]
   75 |     int cnt = 0;
      |         ^~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 9368 KB Output is correct
2 Correct 67 ms 9136 KB Output is correct
3 Incorrect 62 ms 9392 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1735 ms 16664 KB Output is correct
2 Correct 1780 ms 16660 KB Output is correct
3 Correct 47 ms 9136 KB Output is correct
4 Correct 1800 ms 16664 KB Output is correct
5 Correct 1912 ms 16656 KB Output is correct
6 Correct 2041 ms 17244 KB Output is correct
7 Correct 1645 ms 16656 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4568 ms 10424 KB Output is correct
2 Correct 4732 ms 10412 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 1951 ms 10480 KB Output is correct
5 Correct 1871 ms 10412 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4568 ms 10424 KB Output is correct
2 Correct 4732 ms 10412 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 1951 ms 10480 KB Output is correct
5 Correct 1871 ms 10412 KB Output is correct
6 Correct 4521 ms 10524 KB Output is correct
7 Correct 4614 ms 10412 KB Output is correct
8 Correct 1 ms 2384 KB Output is correct
9 Incorrect 1 ms 2384 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 9368 KB Output is correct
2 Correct 67 ms 9136 KB Output is correct
3 Incorrect 62 ms 9392 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 9368 KB Output is correct
2 Correct 67 ms 9136 KB Output is correct
3 Incorrect 62 ms 9392 KB Output isn't correct
4 Halted 0 ms 0 KB -