oj.uz

Submission #393040

# Submission time Handle Problem Language Result Execution time Memory
393040 2021-04-22T15:26:39 Z nvmdava Road Construction (JOI21_road_construction) C++17
100 / 100
 1103 ms 25052 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];
int n;
ll k;

int fen[N];

void update(int x, int v){
    while(x <= n){
        fen[x] += v;
        x += x & -x;
    }
}

int query(int x){
    int res = 0;
    while(x){
        res += fen[x];
        x -= x & -x;
    }
    return res;
}
 
vector<ll> ans;
int l1[N], r1[N];
bool count(ll len){
    ll cnt = 0;
    l1[0] = 1;
    r1[0] = 1;
    for(int i = 1; i <= n; ++i){
        l1[i] = l1[i - 1];
        while(a[l1[i]] < a[i] - len)
            ++l1[i];
        r1[i] = r1[i - 1];
        while(r1[i] < n && a[r1[i] + 1] <= a[i] + len)
            ++r1[i];
    }

    int l = 1;
    for(int i = 1; i <= n; ++i){
        while(b[l] < b[i] - len)
            update(w[l++], -1);
        cnt += query(r1[w[i]]) - query(l1[w[i]] - 1);
        if(cnt >= k){
            for(; l < i; ++l)
                update(w[l], -1);
            return 0;
        }

        update(w[i], 1);
    }
    for(; l <= n; ++l)
        update(w[l], -1);
    return 1;
}

void find(ll len){
    set<pair<ll, int> > in;
    int l = 1;
    for(int i = 1; i <= n; ++i){
        while(a[l] < a[i] - len){
            in.erase({b[rev[l]], l});
            ++l;
        }
        auto it = in.lower_bound({b[rev[i]] - len, 0});
        while(it != in.end() && it -> ff <= b[rev[i]] + len){
            ans.push_back(max(abs(b[rev[i]] - it -> ff), abs(a[i] - a[it -> ss])));
            ++it;
        }
        in.insert({b[rev[i]], i});
    }
}
 
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;
    }
    
    ll len = 0;
    for(int i = 31; i >= 0; --i)
        if(count((1LL << i) | len))
            len |= 1LL << i;
    find(len);
    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 'int main()':
road_construction.cpp:118: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]
  118 |     while(ans.size() < k)
      |           ~~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 5108 KB Output is correct
2 Correct 55 ms 5116 KB Output is correct
3 Correct 52 ms 5168 KB Output is correct
4 Correct 54 ms 5124 KB Output is correct
5 Correct 51 ms 3964 KB Output is correct
6 Correct 3 ms 460 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 584 ms 23296 KB Output is correct
2 Correct 589 ms 23212 KB Output is correct
3 Correct 48 ms 5064 KB Output is correct
4 Correct 474 ms 22996 KB Output is correct
5 Correct 356 ms 23232 KB Output is correct
6 Correct 384 ms 23232 KB Output is correct
7 Correct 389 ms 22516 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 18172 KB Output is correct
2 Correct 646 ms 18216 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 261 ms 18180 KB Output is correct
5 Correct 575 ms 18164 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 18172 KB Output is correct
2 Correct 646 ms 18216 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 261 ms 18180 KB Output is correct
5 Correct 575 ms 18164 KB Output is correct
6 Correct 728 ms 18184 KB Output is correct
7 Correct 691 ms 18160 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 695 ms 18160 KB Output is correct
11 Correct 236 ms 18112 KB Output is correct
12 Correct 575 ms 18204 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 5108 KB Output is correct
2 Correct 55 ms 5116 KB Output is correct
3 Correct 52 ms 5168 KB Output is correct
4 Correct 54 ms 5124 KB Output is correct
5 Correct 51 ms 3964 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 455 ms 11516 KB Output is correct
8 Correct 455 ms 11524 KB Output is correct
9 Correct 52 ms 5236 KB Output is correct
10 Correct 420 ms 10748 KB Output is correct
11 Correct 261 ms 10776 KB Output is correct
12 Correct 303 ms 11428 KB Output is correct
13 Correct 255 ms 10528 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 5108 KB Output is correct
2 Correct 55 ms 5116 KB Output is correct
3 Correct 52 ms 5168 KB Output is correct
4 Correct 54 ms 5124 KB Output is correct
5 Correct 51 ms 3964 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 584 ms 23296 KB Output is correct
8 Correct 589 ms 23212 KB Output is correct
9 Correct 48 ms 5064 KB Output is correct
10 Correct 474 ms 22996 KB Output is correct
11 Correct 356 ms 23232 KB Output is correct
12 Correct 384 ms 23232 KB Output is correct
13 Correct 389 ms 22516 KB Output is correct
14 Correct 486 ms 18172 KB Output is correct
15 Correct 646 ms 18216 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 261 ms 18180 KB Output is correct
18 Correct 575 ms 18164 KB Output is correct
19 Correct 728 ms 18184 KB Output is correct
20 Correct 691 ms 18160 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 695 ms 18160 KB Output is correct
24 Correct 236 ms 18112 KB Output is correct
25 Correct 575 ms 18204 KB Output is correct
26 Correct 455 ms 11516 KB Output is correct
27 Correct 455 ms 11524 KB Output is correct
28 Correct 52 ms 5236 KB Output is correct
29 Correct 420 ms 10748 KB Output is correct
30 Correct 261 ms 10776 KB Output is correct
31 Correct 303 ms 11428 KB Output is correct
32 Correct 255 ms 10528 KB Output is correct
33 Correct 1103 ms 24076 KB Output is correct
34 Correct 1099 ms 25032 KB Output is correct
35 Correct 940 ms 24268 KB Output is correct
36 Correct 662 ms 24812 KB Output is correct
37 Correct 694 ms 25052 KB Output is correct
38 Correct 664 ms 23604 KB Output is correct