oj.uz

Submission #392958

# Submission time Handle Problem Language Result Execution time Memory
392958 2021-04-22T12:33:56 Z nvmdava Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 240740 KB 
#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;
 
struct Node{
    Node *le, *ri;
    int cnt = 0;
    int query(int l, int r, int L, int R){
        if(l > R || r < L) return 0;
        if(cnt == 0) return 0;
        if(L <= l && r <= R) return cnt;
        int m = (l + r) >> 1;
        return le -> query(l, m, L, R) + ri -> query(m + 1, r, L, R);
    }
    Node* update(int l, int r, int x){
        if(l > x || r < x) return this;
        Node* ret = new Node();
        if(l == r){
            ret -> cnt = 1;
            return ret;
        }
        ret -> le = le;
        ret -> ri = ri;
        int m = (l + r) >> 1;
        ret -> le = ret -> le -> update(l, m, x);
        ret -> ri = ret -> ri -> update(m + 1, r, x);
        ret -> cnt = ret -> le -> cnt + ret -> ri -> cnt;
        return ret;
    }
};
 
void buildd(Node* pnt, int l, int r){
    if(l == r) return;
    int m = (l + r) >> 1;
    pnt -> le = new Node();
    pnt -> ri = new Node();
    buildd(pnt -> le, l, m);
    buildd(pnt -> ri, m + 1, r);
}
 
Node* tree[N];
 
vector<ll> ans;
void find(int id, int l, int r, int L, int R, int le, int ri, int x){
    if(l > R || r < L) return;
    if(L <= l && r <= R){
        le = lower_bound(seg[id].begin(), seg[id].end(), le) - seg[id].begin();
        for(int i = le; i < seg[id].size() && seg[id][i] <= ri; ++i)
            ans.push_back(max(a[x] - a[seg[id][i]], abs(b[rev[x]] - b[rev[seg[id][i]]])));
        return;
    }
    int m = (l + r) >> 1;
    find(id << 1, l, m, L, R, le, ri, x);
    find(id << 1 | 1, m + 1, r, L, R, le, ri, x);
    return;
}
 
bool count(ll len, bool get){
    ll cnt = 0;
    for(int i = n; i > 1; --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;
        if(get)
            find(1, 1, n, l2, r2, l1, r1, i);
        else
            cnt += tree[r2]->query(1, n, l1, r1) - tree[l2 - 1]->query(1, n, l1, r1);
        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);
    tree[0] = new Node();
    buildd(tree[0], 1, n);
    for(int i = 1; i <= n; ++i)
        tree[i] = tree[i - 1] -> update(1, n, w[i]);
    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';
}

Compilation message

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 'void find(int, int, int, int, int, int, int, int)':
road_construction.cpp:85:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         for(int i = le; i < seg[id].size() && seg[id][i] <= ri; ++i)
      |                         ~~^~~~~~~~~~~~~~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:148: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]
  148 |     while(ans.size() < k)
      |           ~~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 28984 KB Output is correct
2 Correct 74 ms 29036 KB Output is correct
3 Correct 65 ms 28992 KB Output is correct
4 Correct 66 ms 28988 KB Output is correct
5 Correct 75 ms 27984 KB Output is correct
6 Correct 23 ms 24396 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2141 ms 240712 KB Output is correct
2 Correct 2096 ms 240664 KB Output is correct
3 Correct 66 ms 28808 KB Output is correct
4 Correct 864 ms 240528 KB Output is correct
5 Correct 1888 ms 240728 KB Output is correct
6 Correct 2029 ms 240740 KB Output is correct
7 Correct 1765 ms 240068 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3226 ms 235388 KB Output is correct
2 Correct 3073 ms 235496 KB Output is correct
3 Correct 16 ms 23756 KB Output is correct
4 Correct 590 ms 235440 KB Output is correct
5 Correct 5375 ms 235424 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3226 ms 235388 KB Output is correct
2 Correct 3073 ms 235496 KB Output is correct
3 Correct 16 ms 23756 KB Output is correct
4 Correct 590 ms 235440 KB Output is correct
5 Correct 5375 ms 235424 KB Output is correct
6 Correct 6127 ms 235528 KB Output is correct
7 Correct 5923 ms 235540 KB Output is correct
8 Correct 16 ms 23756 KB Output is correct
9 Correct 15 ms 23852 KB Output is correct
10 Correct 4141 ms 235552 KB Output is correct
11 Correct 558 ms 235416 KB Output is correct
12 Correct 5326 ms 235412 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 28984 KB Output is correct
2 Correct 74 ms 29036 KB Output is correct
3 Correct 65 ms 28992 KB Output is correct
4 Correct 66 ms 28988 KB Output is correct
5 Correct 75 ms 27984 KB Output is correct
6 Correct 23 ms 24396 KB Output is correct
7 Correct 4489 ms 109112 KB Output is correct
8 Correct 4481 ms 109288 KB Output is correct
9 Correct 68 ms 28988 KB Output is correct
10 Correct 3657 ms 108524 KB Output is correct
11 Correct 1446 ms 108436 KB Output is correct
12 Correct 2830 ms 109288 KB Output is correct
13 Correct 1764 ms 108264 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 28984 KB Output is correct
2 Correct 74 ms 29036 KB Output is correct
3 Correct 65 ms 28992 KB Output is correct
4 Correct 66 ms 28988 KB Output is correct
5 Correct 75 ms 27984 KB Output is correct
6 Correct 23 ms 24396 KB Output is correct
7 Correct 2141 ms 240712 KB Output is correct
8 Correct 2096 ms 240664 KB Output is correct
9 Correct 66 ms 28808 KB Output is correct
10 Correct 864 ms 240528 KB Output is correct
11 Correct 1888 ms 240728 KB Output is correct
12 Correct 2029 ms 240740 KB Output is correct
13 Correct 1765 ms 240068 KB Output is correct
14 Correct 3226 ms 235388 KB Output is correct
15 Correct 3073 ms 235496 KB Output is correct
16 Correct 16 ms 23756 KB Output is correct
17 Correct 590 ms 235440 KB Output is correct
18 Correct 5375 ms 235424 KB Output is correct
19 Correct 6127 ms 235528 KB Output is correct
20 Correct 5923 ms 235540 KB Output is correct
21 Correct 16 ms 23756 KB Output is correct
22 Correct 15 ms 23852 KB Output is correct
23 Correct 4141 ms 235552 KB Output is correct
24 Correct 558 ms 235416 KB Output is correct
25 Correct 5326 ms 235412 KB Output is correct
26 Correct 4489 ms 109112 KB Output is correct
27 Correct 4481 ms 109288 KB Output is correct
28 Correct 68 ms 28988 KB Output is correct
29 Correct 3657 ms 108524 KB Output is correct
30 Correct 1446 ms 108436 KB Output is correct
31 Correct 2830 ms 109288 KB Output is correct
32 Correct 1764 ms 108264 KB Output is correct
33 Execution timed out 10109 ms 235376 KB Time limit exceeded
34 Halted 0 ms 0 KB -