oj.uz

Submission #1112061

# Submission time Handle Problem Language Result Execution time Memory
1112061 2024-11-13T15:32:07 Z onbert Road Construction (JOI21_road_construction) C++17
6 / 100
 4699 ms 16668 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;
    set<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)));
                cnt++;
                assert(cnt <= 2*k);
                // cout << max(abs(a[i].first - cur.second), abs(a[i].second - cur.first)) << endl;
            }
            it++;
        }
    }
    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:99: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]
   99 |     while (ans.size() < 2*k) ans.push_back(L);
      |            ~~~~~~~~~~~^~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 9368 KB Output is correct
2 Correct 57 ms 9348 KB Output is correct
3 Runtime error 20 ms 13668 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1815 ms 16660 KB Output is correct
2 Correct 1732 ms 16492 KB Output is correct
3 Correct 49 ms 9116 KB Output is correct
4 Correct 1873 ms 16660 KB Output is correct
5 Correct 1988 ms 16656 KB Output is correct
6 Correct 2033 ms 16668 KB Output is correct
7 Correct 1746 ms 16660 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4623 ms 10412 KB Output is correct
2 Correct 4699 ms 10452 KB Output is correct
3 Runtime error 4 ms 4688 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4623 ms 10412 KB Output is correct
2 Correct 4699 ms 10452 KB Output is correct
3 Runtime error 4 ms 4688 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 9368 KB Output is correct
2 Correct 57 ms 9348 KB Output is correct
3 Runtime error 20 ms 13668 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 9368 KB Output is correct
2 Correct 57 ms 9348 KB Output is correct
3 Runtime error 20 ms 13668 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -