oj.uz

답안 #907431

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
907431 2024-01-15T14:33:39 Z lighton Road Construction (JOI21_road_construction) C++17
32 / 100
 7827 ms 55876 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{
    Node node[2000001];
    int sz = 1;
    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 = sz; node[now].r = node[prv].r;
            sz++;
            update(node[now].l,node[prv].l,s,m,f,x);
        }
        else{
            node[now].r = sz; node[now].l = node[prv].l;
            sz++;
            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.sz; pst.sz++;
        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:37:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |         int m = s+e>>1;
      |                 ~^~
road_construction.cpp: In member function 'int PST::query(int, int, int, int)':
road_construction.cpp:54:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |         int m = s+e>>1;
      |                 ~^~
road_construction.cpp: In function 'll findmin(ll, ll, int, int)':
road_construction.cpp:73:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |         m = l+r>>1;
      |             ~^~
road_construction.cpp: In function 'int main()':
road_construction.cpp:121:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |     scanf("%d %d" , &N,&K);
      |     ~~~~~^~~~~~~~~~~~~~~~~
road_construction.cpp:122:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |     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:78:13: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
   78 |             if(s==1) r=m;
      |             ^~
road_construction.cpp:77:35: warning: 'pxe' may be used uninitialized in this function [-Wmaybe-uninitialized]
   77 |         if(pys == ys && pye == ye && pxe == xe){
      |            ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
road_construction.cpp:77:29: warning: 'pye' may be used uninitialized in this function [-Wmaybe-uninitialized]
   77 |         if(pys == ys && pye == ye && pxe == xe){
      |                         ~~~~^~~~~
road_construction.cpp:77:16: warning: 'pys' may be used uninitialized in this function [-Wmaybe-uninitialized]
   77 |         if(pys == ys && pye == ye && pxe == xe){
      |            ~~~~^~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1431 ms 13316 KB Output is correct
2 Correct 1434 ms 13368 KB Output is correct
3 Correct 1157 ms 13508 KB Output is correct
4 Correct 1039 ms 13276 KB Output is correct
5 Correct 1305 ms 11968 KB Output is correct
6 Correct 9 ms 10588 KB Output is correct

Subtask #2
0 / 6.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 20.0

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

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1431 ms 13316 KB Output is correct
2 Correct 1434 ms 13368 KB Output is correct
3 Correct 1157 ms 13508 KB Output is correct
4 Correct 1039 ms 13276 KB Output is correct
5 Correct 1305 ms 11968 KB Output is correct
6 Correct 9 ms 10588 KB Output is correct
7 Correct 7827 ms 43064 KB Output is correct
8 Correct 7708 ms 42704 KB Output is correct
9 Correct 1034 ms 13392 KB Output is correct
10 Correct 3130 ms 41988 KB Output is correct
11 Correct 3943 ms 41736 KB Output is correct
12 Correct 1406 ms 34384 KB Output is correct
13 Correct 1836 ms 35140 KB Output is correct

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1431 ms 13316 KB Output is correct
2 Correct 1434 ms 13368 KB Output is correct
3 Correct 1157 ms 13508 KB Output is correct
4 Correct 1039 ms 13276 KB Output is correct
5 Correct 1305 ms 11968 KB Output is correct
6 Correct 9 ms 10588 KB Output is correct
7 Incorrect 4721 ms 55876 KB Output isn't correct
8 Halted 0 ms 0 KB -