oj.uz

Submission #1112059

# Submission time Handle Problem Language Result Execution time Memory
1112059 2024-11-13T15:23:53 Z onbert Road Construction (JOI21_road_construction) C++17
13 / 100
 4869 ms 19684 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;
    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 != s.end() && 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)));
                // 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:96: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]
   96 |     while (ans.size() < 2*k) ans.push_back(L);
      |            ~~~~~~~~~~~^~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 9392 KB Output is correct
2 Correct 59 ms 9392 KB Output is correct
3 Incorrect 59 ms 9392 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1836 ms 19684 KB Output is correct
2 Correct 1827 ms 16660 KB Output is correct
3 Correct 48 ms 9136 KB Output is correct
4 Correct 1917 ms 16660 KB Output is correct
5 Correct 2115 ms 16660 KB Output is correct
6 Correct 2069 ms 16660 KB Output is correct
7 Correct 1702 ms 16660 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4660 ms 10932 KB Output is correct
2 Correct 4869 ms 15532 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 2077 ms 13484 KB Output is correct
5 Correct 1506 ms 14828 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4660 ms 10932 KB Output is correct
2 Correct 4869 ms 15532 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 2077 ms 13484 KB Output is correct
5 Correct 1506 ms 14828 KB Output is correct
6 Correct 4678 ms 14508 KB Output is correct
7 Correct 4834 ms 15020 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

# Verdict Execution time Memory Grader output
1 Correct 59 ms 9392 KB Output is correct
2 Correct 59 ms 9392 KB Output is correct
3 Incorrect 59 ms 9392 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 9392 KB Output is correct
2 Correct 59 ms 9392 KB Output is correct
3 Incorrect 59 ms 9392 KB Output isn't correct
4 Halted 0 ms 0 KB -