oj.uz

Submission #387749

# Submission time Handle Problem Language Result Execution time Memory
387749 2021-04-09T07:15:38 Z abc864197532 Road Construction (JOI21_road_construction) C++17
38 / 100
 10000 ms 15596 KB 
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define test(x) cout << "Line(" << __LINE__ << ") " #x << ' ' << x << endl
#define printv(x) {\
	for (auto i : x) cout << i << ' ';\
	cout << endl;\
}
#define pii pair <int, int>
#define pll pair <lli, lli>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
template<typename A, typename B>
ostream& operator << (ostream& o, pair<A, B> a){
    return o << a.X << ' ' << a.Y;
}
template<typename A, typename B>
istream& operator >> (istream& o, pair<A, B> &a){
    return o >> a.X >> a.Y;
}
const int mod = 1e9 + 7, abc = 864197532, N = 300001, K = 111;

struct Pt {
    lli x, y, idx;
    Pt (lli _x = 0, lli _y = 0) : x(_x), y(_y) {}
    bool operator < (const Pt &o) const {
        return x < o.x;
    }
};

struct cmp {
    bool operator () (const Pt &a, const Pt &b) const {
        if (a.y == b.y) return a.idx < b.idx;
        return a.y < b.y;
    }
};

int bit[N];

void reset() {
    for (int i = 0; i < N; ++i) bit[i] = 0;
}

void add(int p, int v) {
    for (int i = p; i < N; i += i & (-i)) bit[i] += v;
}

int query(int p) {
    int ans = 0;
    for (int i = p; i > 0; i -= i & (-i)) ans += bit[i];
    return ans;
}

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector <Pt> a;
    for (int i = 0, x, y; i < n; ++i) {
        cin >> x >> y;
        a.pb(Pt(x + y, x - y));
        a.back().idx = i;
    }
    vector <lli> y_idx;
    for (int i = 0; i < n; ++i) y_idx.pb(a[i].y);
    sort(all(y_idx));
    y_idx.resize(unique(all(y_idx)) - y_idx.begin());
    auto get = [&](lli x) {
        return lower_bound(all(y_idx), x) - y_idx.begin() + 5;
    };
    sort(all(a));
    auto chk = [&](lli d) {
        /*
         * 2 4 8 9 15
         * 4 9
         */
        reset();
        lli ans = 0;
        for (int i = 0, j = 0; i < n; ++i) {
            while (j < n && a[j].x + d < a[i].x) add(get(a[j++].y), -1);
            ans += query(get(a[i].y + d + 1) - 1) - query(get(a[i].y - d) - 1);
            add(get(a[i].y), 1);
        }
        return ans;
    };
    lli l = 0, r = 4e9 + 87;
    while (r - l > 1) {
        ((chk(l + r >> 1)) < k ? l : r) = l + r >> 1;
    }
    lli d = l;
    l = 0, r = 4e9 + 87;
    while (r - l > 1) {
        ((chk(l + r >> 1)) >= k ? r : l) = l + r >> 1;
    }
    vector <lli> ans;
    set <Pt, cmp> s;
    for (int i = 0, j = 0; i < n; ++i) {
        while (j < n && a[j].x + d < a[i].x) s.erase(a[j++]);
        for (auto it = s.lower_bound(Pt(0, a[i].y - d)); it != s.end() && it->y <= a[i].y + d; ++it) {
            ans.pb(max(a[i].x - it->x, abs(it->y - a[i].y)));
        }
        s.insert(a[i]);
    }
    sort(all(ans));
    for (int i = 0; i < k; ++i) {
        if (i < ans.size()) cout << ans[i] << '\n';
        else cout << r << '\n';
    }
}

Compilation message

road_construction.cpp: In function 'int main()':
road_construction.cpp:94:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |         ((chk(l + r >> 1)) < k ? l : r) = l + r >> 1;
      |               ~~^~~
road_construction.cpp:94:45: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |         ((chk(l + r >> 1)) < k ? l : r) = l + r >> 1;
      |                                           ~~^~~
road_construction.cpp:99:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |         ((chk(l + r >> 1)) >= k ? r : l) = l + r >> 1;
      |               ~~^~~
road_construction.cpp:99:46: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |         ((chk(l + r >> 1)) >= k ? r : l) = l + r >> 1;
      |                                            ~~^~~
road_construction.cpp:112:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |         if (i < ans.size()) cout << ans[i] << '\n';
      |             ~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 6108 KB Output is correct
2 Correct 81 ms 6116 KB Output is correct
3 Correct 79 ms 6192 KB Output is correct
4 Correct 69 ms 6244 KB Output is correct
5 Correct 75 ms 5064 KB Output is correct
6 Correct 23 ms 1532 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4644 ms 15528 KB Output is correct
2 Correct 4658 ms 15468 KB Output is correct
3 Correct 65 ms 6120 KB Output is correct
4 Correct 4744 ms 15352 KB Output is correct
5 Correct 4657 ms 15596 KB Output is correct
6 Correct 4645 ms 15592 KB Output is correct
7 Correct 4589 ms 14840 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10058 ms 11300 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10058 ms 11300 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 6108 KB Output is correct
2 Correct 81 ms 6116 KB Output is correct
3 Correct 79 ms 6192 KB Output is correct
4 Correct 69 ms 6244 KB Output is correct
5 Correct 75 ms 5064 KB Output is correct
6 Correct 23 ms 1532 KB Output is correct
7 Correct 4137 ms 11156 KB Output is correct
8 Correct 4145 ms 11088 KB Output is correct
9 Correct 72 ms 6304 KB Output is correct
10 Correct 3825 ms 10388 KB Output is correct
11 Correct 3643 ms 10244 KB Output is correct
12 Correct 1697 ms 7608 KB Output is correct
13 Correct 1760 ms 9624 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 6108 KB Output is correct
2 Correct 81 ms 6116 KB Output is correct
3 Correct 79 ms 6192 KB Output is correct
4 Correct 69 ms 6244 KB Output is correct
5 Correct 75 ms 5064 KB Output is correct
6 Correct 23 ms 1532 KB Output is correct
7 Correct 4644 ms 15528 KB Output is correct
8 Correct 4658 ms 15468 KB Output is correct
9 Correct 65 ms 6120 KB Output is correct
10 Correct 4744 ms 15352 KB Output is correct
11 Correct 4657 ms 15596 KB Output is correct
12 Correct 4645 ms 15592 KB Output is correct
13 Correct 4589 ms 14840 KB Output is correct
14 Execution timed out 10058 ms 11300 KB Time limit exceeded
15 Halted 0 ms 0 KB -