oj.uz

답안 #393012

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
393012 2021-04-22T14:20:18 Z nvmdava Road Construction (JOI21_road_construction) C++17
13 / 100
 5519 ms 190228 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;
 
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(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;
int l1[N], r1[N], l2[N], r2[N];
bool count(ll len){
    ll cnt = 0;
    l1[0] = 1;
    r1[0] = 0;
    l2[0] = 1;
    r2[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] = i - 1;
        l2[i] = l2[i - 1];
        while(b[l2[i]] < b[i] - len)
            ++l2[i];
        r2[i] = r2[i - 1];
        while(r2[i] + 1 <= n && b[r2[i] + 1] <= b[i] + len)
            ++r2[i];
    }
    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[i] > r1[i] || l2[rev[i]] > r2[rev[i]]) continue;
        cnt += tree[r2[rev[i]]]->query(1, n, l1[i], r1[i]) - tree[l2[rev[i]] - 1]->query(1, n, l1[i], r1[i]);
        if(cnt >= k) return 0;
    }
    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]], rev[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]], rev[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;
    }
    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 = 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:139: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]
  139 |     while(ans.size() < k)
      |           ~~~~~~~~~~~^~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 60 ms 5552 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1784 ms 190172 KB Output is correct
2 Correct 1868 ms 190152 KB Output is correct
3 Correct 52 ms 5296 KB Output is correct
4 Correct 797 ms 190052 KB Output is correct
5 Correct 1624 ms 190228 KB Output is correct
6 Correct 1836 ms 190208 KB Output is correct
7 Correct 1440 ms 189472 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2899 ms 184912 KB Output is correct
2 Correct 2804 ms 184908 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 434 ms 184996 KB Output is correct
5 Correct 4124 ms 185036 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2899 ms 184912 KB Output is correct
2 Correct 2804 ms 184908 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 434 ms 184996 KB Output is correct
5 Correct 4124 ms 185036 KB Output is correct
6 Incorrect 5519 ms 184956 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 60 ms 5552 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 60 ms 5552 KB Output isn't correct
2 Halted 0 ms 0 KB -