oj.uz

답안 #392952

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
392952 2021-04-22T11:43:53 Z nvmdava Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 74744 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;
vector<ll> ans;
int query(int id, int l, int r, int L, int R, int le, int ri, int x){
    if(l > R || r < L) return 0;
    if(L <= l && r <= R){
        le = lower_bound(seg[id].begin(), seg[id].end(), le) - seg[id].begin();
        ri = upper_bound(seg[id].begin(), seg[id].end(), ri) - seg[id].begin() - 1;
        if(x)
            for(int i = le; i <= ri; ++i)
                ans.push_back(max(abs(a[x] - a[seg[id][i]]), abs(b[rev[x]] - b[rev[seg[id][i]]])));
        return ri - le + 1;
    }
    int m = (l + r) >> 1;
    return query(id << 1, l, m, L, R, le, ri, x) + query(id << 1 | 1, m + 1, r, L, R, le, ri, x);
}

bool count(ll len, bool get){
    ll cnt = 0;
    for(int i = n; i > 0; --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;
        cnt += query(1, 1, n, l2, r2, l1, r1, get * i);
        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);
    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 'int main()':
road_construction.cpp:102: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]
  102 |     while(ans.size() < k)
      |           ~~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 28600 KB Output is correct
2 Correct 87 ms 28560 KB Output is correct
3 Correct 67 ms 28748 KB Output is correct
4 Correct 65 ms 28756 KB Output is correct
5 Correct 74 ms 27472 KB Output is correct
6 Correct 29 ms 23992 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1470 ms 74568 KB Output is correct
2 Correct 1465 ms 74656 KB Output is correct
3 Correct 61 ms 28472 KB Output is correct
4 Correct 635 ms 74536 KB Output is correct
5 Correct 1328 ms 74680 KB Output is correct
6 Correct 1421 ms 74744 KB Output is correct
7 Correct 1253 ms 73980 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1701 ms 70376 KB Output is correct
2 Correct 1699 ms 70480 KB Output is correct
3 Correct 15 ms 23756 KB Output is correct
4 Correct 372 ms 70340 KB Output is correct
5 Correct 5660 ms 70436 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1701 ms 70376 KB Output is correct
2 Correct 1699 ms 70480 KB Output is correct
3 Correct 15 ms 23756 KB Output is correct
4 Correct 372 ms 70340 KB Output is correct
5 Correct 5660 ms 70436 KB Output is correct
6 Correct 3902 ms 70360 KB Output is correct
7 Correct 3651 ms 70480 KB Output is correct
8 Correct 14 ms 23756 KB Output is correct
9 Correct 14 ms 23784 KB Output is correct
10 Correct 2364 ms 70408 KB Output is correct
11 Correct 315 ms 70424 KB Output is correct
12 Correct 5599 ms 70472 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 28600 KB Output is correct
2 Correct 87 ms 28560 KB Output is correct
3 Correct 67 ms 28748 KB Output is correct
4 Correct 65 ms 28756 KB Output is correct
5 Correct 74 ms 27472 KB Output is correct
6 Correct 29 ms 23992 KB Output is correct
7 Correct 5207 ms 48692 KB Output is correct
8 Correct 5245 ms 48688 KB Output is correct
9 Correct 76 ms 28756 KB Output is correct
10 Correct 3125 ms 47972 KB Output is correct
11 Correct 1101 ms 47828 KB Output is correct
12 Correct 2972 ms 48696 KB Output is correct
13 Correct 1980 ms 47152 KB Output is correct

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 28600 KB Output is correct
2 Correct 87 ms 28560 KB Output is correct
3 Correct 67 ms 28748 KB Output is correct
4 Correct 65 ms 28756 KB Output is correct
5 Correct 74 ms 27472 KB Output is correct
6 Correct 29 ms 23992 KB Output is correct
7 Correct 1470 ms 74568 KB Output is correct
8 Correct 1465 ms 74656 KB Output is correct
9 Correct 61 ms 28472 KB Output is correct
10 Correct 635 ms 74536 KB Output is correct
11 Correct 1328 ms 74680 KB Output is correct
12 Correct 1421 ms 74744 KB Output is correct
13 Correct 1253 ms 73980 KB Output is correct
14 Correct 1701 ms 70376 KB Output is correct
15 Correct 1699 ms 70480 KB Output is correct
16 Correct 15 ms 23756 KB Output is correct
17 Correct 372 ms 70340 KB Output is correct
18 Correct 5660 ms 70436 KB Output is correct
19 Correct 3902 ms 70360 KB Output is correct
20 Correct 3651 ms 70480 KB Output is correct
21 Correct 14 ms 23756 KB Output is correct
22 Correct 14 ms 23784 KB Output is correct
23 Correct 2364 ms 70408 KB Output is correct
24 Correct 315 ms 70424 KB Output is correct
25 Correct 5599 ms 70472 KB Output is correct
26 Correct 5207 ms 48692 KB Output is correct
27 Correct 5245 ms 48688 KB Output is correct
28 Correct 76 ms 28756 KB Output is correct
29 Correct 3125 ms 47972 KB Output is correct
30 Correct 1101 ms 47828 KB Output is correct
31 Correct 2972 ms 48696 KB Output is correct
32 Correct 1980 ms 47152 KB Output is correct
33 Execution timed out 10091 ms 70644 KB Time limit exceeded
34 Halted 0 ms 0 KB -