oj.uz

Submission #392959

# Submission time Handle Problem Language Result Execution time Memory
392959 2021-04-22T12:37:07 Z nvmdava Road Construction (JOI21_road_construction) C++17
38 / 100
 10000 ms 240664 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 77 ms 28984 KB Output is correct
2 Correct 79 ms 29064 KB Output is correct
3 Correct 68 ms 28984 KB Output is correct
4 Correct 69 ms 29016 KB Output is correct
5 Correct 71 ms 27960 KB Output is correct
6 Correct 29 ms 24424 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4651 ms 240572 KB Output is correct
2 Correct 5142 ms 240656 KB Output is correct
3 Correct 63 ms 28788 KB Output is correct
4 Correct 4041 ms 240408 KB Output is correct
5 Correct 5416 ms 240664 KB Output is correct
6 Correct 5517 ms 240664 KB Output is correct
7 Correct 4435 ms 239928 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10107 ms 235488 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 10107 ms 235488 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 28984 KB Output is correct
2 Correct 79 ms 29064 KB Output is correct
3 Correct 68 ms 28984 KB Output is correct
4 Correct 69 ms 29016 KB Output is correct
5 Correct 71 ms 27960 KB Output is correct
6 Correct 29 ms 24424 KB Output is correct
7 Correct 5909 ms 109216 KB Output is correct
8 Correct 6114 ms 109216 KB Output is correct
9 Correct 69 ms 28984 KB Output is correct
10 Correct 5536 ms 108488 KB Output is correct
11 Correct 3646 ms 108320 KB Output is correct
12 Correct 4575 ms 109216 KB Output is correct
13 Correct 4252 ms 108192 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 28984 KB Output is correct
2 Correct 79 ms 29064 KB Output is correct
3 Correct 68 ms 28984 KB Output is correct
4 Correct 69 ms 29016 KB Output is correct
5 Correct 71 ms 27960 KB Output is correct
6 Correct 29 ms 24424 KB Output is correct
7 Correct 4651 ms 240572 KB Output is correct
8 Correct 5142 ms 240656 KB Output is correct
9 Correct 63 ms 28788 KB Output is correct
10 Correct 4041 ms 240408 KB Output is correct
11 Correct 5416 ms 240664 KB Output is correct
12 Correct 5517 ms 240664 KB Output is correct
13 Correct 4435 ms 239928 KB Output is correct
14 Execution timed out 10107 ms 235488 KB Time limit exceeded
15 Halted 0 ms 0 KB -