oj.uz

답안 #907430

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
907430 2024-01-15T14:28:09 Z lighton Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 126860 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#define forf(i,a,b) for(int i = a; i<=b; i++)
#define all(v) v.begin(),v.end()
#define comp(v) v.erase(unique(all(v)),v.end())
#define LB(i,v) lower_bound(all(v),i)-v.begin() // 1-based
#define UB(i,v) upper_bound(all(v),i)-v.begin()

#define fi first
#define se second
using namespace std;
typedef long long ll;
int N,K,YS;
ll X[1000001],Y[1000001];
struct dot{
    ll x,y,id;
    bool operator<(const dot &r) const{
        if(x==r.x) return id<r.id;
        return x<r.x;
    }
} A[1000001];
vector<ll> xl,yl;
ll inf = 1e18;
ll ab(ll x){ return x<0?-x:x;}
struct Node{
    int val;
    int l,r;
} def = {0,0,0};
struct PST{
    vector<Node> node = {def};
    int root[1000001];
    void update(int now , int prv, int s, int e, int f, int x){
        if(s==e) {node[now].val = node[prv].val + x; return; }
        int m = s+e>>1;
        if(f<=m){
            node[now].l = node.size(); node[now].r = node[prv].r;
            node.push_back(def);
            update(node[now].l,node[prv].l,s,m,f,x);
        }
        else{
            node[now].r = node.size(); node[now].l = node[prv].l;
            node.push_back(def);
            update(node[now].r,node[prv].r,m+1,e,f,x);
        }
        node[now].val = node[node[now].l].val+node[node[now].r].val;
    }
    int l,r;
    int query(int now ,int prv, int s, int e){
        if(l<=s && e<=r) return node[now].val-node[prv].val;
        if(s>r || e<l) return 0;
        int m = s+e>>1;
        return query(node[now].l,node[prv].l,s,m)+query(node[now].r,node[prv].r,m+1,e);
    }
} pst;

void init(){
    forf(i,1,N){
        pst.root[i] = pst.node.size(); pst.node.push_back(def);
        pst.update(pst.root[i],pst.root[i-1],1,YS,LB(A[i].y,yl)+1,1);
    }
}

ll findmin(ll x, ll y , int xs , int count){
    ll l = 0;
    ll r = 4*1e9;
    ll m;
    int pys,pye,pxe;
    int s;
    while(l+1<r){
        m = l+r>>1;
        int ys = LB(y-m,yl) + 1;
        int ye = UB(y+m,yl)-1 + 1;
        int xe = UB(x+m,xl)-1 + 1;
        if(pys == ys && pye == ye && pxe == xe){
            if(s==1) r=m;
            else l=m;
        }
        pys=ys; pye=ye; pxe=xe;
        pst.l = ys; pst.r = ye;
        int tmp = pst.query(pst.root[xe],pst.root[xs],1,YS);
        if(tmp >= count){r=m; s=1;}
        else {l=m; s =0;}
    }
    return r;
}

int cnt[1000001];
void solve(){
    init();
    priority_queue<pair<ll,int> > pq;
    forf(i,1,N) cnt[i] = 1;
    forf(i,1,N){
        pq.push({-findmin(A[i].x,A[i].y,i,cnt[i]) , i});
        cnt[i]++;
    }
    forf(trash,1,K) {
        printf("%lld\n", -pq.top().first);
        int i = pq.top().second;
        pq.pop();
        pq.push({-findmin(A[i].x,A[i].y,i,cnt[i]) , i});
        cnt[i]++;
    }
}

vector<ll> All;
void naive(){
    forf(i,1,N){
        forf(j,i+1,N){
            All.push_back(max(ab(X[i]-X[j]),ab(Y[i]-Y[j])));
        }
    }
    sort(all(All));
    forf(i,0,K-1) printf("%lld\n" , All[i]);
}


int main(){
    scanf("%d %d" , &N,&K);
    forf(i,1,N) scanf("%lld %lld" , &X[i] , &Y[i]);
    forf(i,1,N){
        ll x = X[i], y = Y[i];
        X[i] = x+y;
        Y[i] = x-y;
        A[i] = {X[i],Y[i],i};
        yl.push_back(Y[i]);
        xl.push_back(X[i]);
    }
    sort(all(yl)); comp(yl); YS=yl.size();
    sort(all(xl));
    sort(A+1,A+N+1);
    solve();
}

Compilation message

road_construction.cpp: In member function 'void PST::update(int, int, int, int, int, int)':
road_construction.cpp:36:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |         int m = s+e>>1;
      |                 ~^~
road_construction.cpp: In member function 'int PST::query(int, int, int, int)':
road_construction.cpp:53:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |         int m = s+e>>1;
      |                 ~^~
road_construction.cpp: In function 'll findmin(ll, ll, int, int)':
road_construction.cpp:72:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |         m = l+r>>1;
      |             ~^~
road_construction.cpp: In function 'int main()':
road_construction.cpp:120:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |     scanf("%d %d" , &N,&K);
      |     ~~~~~^~~~~~~~~~~~~~~~~
road_construction.cpp:121:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |     forf(i,1,N) scanf("%lld %lld" , &X[i] , &Y[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
road_construction.cpp: In function 'll findmin(ll, ll, int, int)':
road_construction.cpp:77:13: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
   77 |             if(s==1) r=m;
      |             ^~
road_construction.cpp:76:35: warning: 'pxe' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |         if(pys == ys && pye == ye && pxe == xe){
      |            ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
road_construction.cpp:76:29: warning: 'pye' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |         if(pys == ys && pye == ye && pxe == xe){
      |                         ~~~~^~~~~
road_construction.cpp:76:16: warning: 'pys' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |         if(pys == ys && pye == ye && pxe == xe){
      |            ~~~~^~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1462 ms 13492 KB Output is correct
2 Correct 1454 ms 13664 KB Output is correct
3 Correct 1173 ms 11424 KB Output is correct
4 Correct 1054 ms 11412 KB Output is correct
5 Correct 1321 ms 12572 KB Output is correct
6 Correct 9 ms 10904 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7443 ms 126372 KB Output is correct
2 Correct 7477 ms 126860 KB Output is correct
3 Correct 1134 ms 11344 KB Output is correct
4 Correct 3895 ms 125492 KB Output is correct
5 Correct 4850 ms 125856 KB Output is correct
6 Correct 4887 ms 124856 KB Output is correct
7 Correct 4190 ms 126800 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4845 ms 125128 KB Output is correct
2 Correct 4824 ms 126336 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2505 ms 126860 KB Output is correct
5 Correct 1555 ms 76444 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4845 ms 125128 KB Output is correct
2 Correct 4824 ms 126336 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2505 ms 126860 KB Output is correct
5 Correct 1555 ms 76444 KB Output is correct
6 Correct 4847 ms 125772 KB Output is correct
7 Correct 4859 ms 126860 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 2 ms 8588 KB Output is correct
10 Correct 4727 ms 125788 KB Output is correct
11 Correct 2493 ms 125580 KB Output is correct
12 Correct 1564 ms 76252 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1462 ms 13492 KB Output is correct
2 Correct 1454 ms 13664 KB Output is correct
3 Correct 1173 ms 11424 KB Output is correct
4 Correct 1054 ms 11412 KB Output is correct
5 Correct 1321 ms 12572 KB Output is correct
6 Correct 9 ms 10904 KB Output is correct
7 Correct 7871 ms 47104 KB Output is correct
8 Correct 7752 ms 45908 KB Output is correct
9 Correct 1059 ms 11604 KB Output is correct
10 Correct 3075 ms 44704 KB Output is correct
11 Correct 3582 ms 43960 KB Output is correct
12 Correct 1392 ms 34980 KB Output is correct
13 Correct 1685 ms 41648 KB Output is correct

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1462 ms 13492 KB Output is correct
2 Correct 1454 ms 13664 KB Output is correct
3 Correct 1173 ms 11424 KB Output is correct
4 Correct 1054 ms 11412 KB Output is correct
5 Correct 1321 ms 12572 KB Output is correct
6 Correct 9 ms 10904 KB Output is correct
7 Correct 7443 ms 126372 KB Output is correct
8 Correct 7477 ms 126860 KB Output is correct
9 Correct 1134 ms 11344 KB Output is correct
10 Correct 3895 ms 125492 KB Output is correct
11 Correct 4850 ms 125856 KB Output is correct
12 Correct 4887 ms 124856 KB Output is correct
13 Correct 4190 ms 126800 KB Output is correct
14 Correct 4845 ms 125128 KB Output is correct
15 Correct 4824 ms 126336 KB Output is correct
16 Correct 2 ms 8540 KB Output is correct
17 Correct 2505 ms 126860 KB Output is correct
18 Correct 1555 ms 76444 KB Output is correct
19 Correct 4847 ms 125772 KB Output is correct
20 Correct 4859 ms 126860 KB Output is correct
21 Correct 2 ms 8540 KB Output is correct
22 Correct 2 ms 8588 KB Output is correct
23 Correct 4727 ms 125788 KB Output is correct
24 Correct 2493 ms 125580 KB Output is correct
25 Correct 1564 ms 76252 KB Output is correct
26 Correct 7871 ms 47104 KB Output is correct
27 Correct 7752 ms 45908 KB Output is correct
28 Correct 1059 ms 11604 KB Output is correct
29 Correct 3075 ms 44704 KB Output is correct
30 Correct 3582 ms 43960 KB Output is correct
31 Correct 1392 ms 34980 KB Output is correct
32 Correct 1685 ms 41648 KB Output is correct
33 Execution timed out 10082 ms 126336 KB Time limit exceeded
34 Halted 0 ms 0 KB -