oj.uz

Submission #907433

# Submission time Handle Problem Language Result Execution time Memory
907433 2024-01-15T14:35:08 Z lighton Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 88660 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[10000001];
    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

# Verdict Execution time Memory Grader output
1 Correct 1422 ms 13088 KB Output is correct
2 Correct 1441 ms 13264 KB Output is correct
3 Correct 1150 ms 13520 KB Output is correct
4 Correct 1037 ms 13432 KB Output is correct
5 Correct 1298 ms 12212 KB Output is correct
6 Correct 9 ms 10788 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7446 ms 88208 KB Output is correct
2 Correct 7428 ms 88640 KB Output is correct
3 Correct 1105 ms 13188 KB Output is correct
4 Correct 3808 ms 87596 KB Output is correct
5 Correct 4783 ms 88660 KB Output is correct
6 Correct 4860 ms 88028 KB Output is correct
7 Correct 4051 ms 87856 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4758 ms 87172 KB Output is correct
2 Correct 4817 ms 87872 KB Output is correct
3 Correct 2 ms 10584 KB Output is correct
4 Correct 2461 ms 86864 KB Output is correct
5 Correct 1584 ms 65436 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4758 ms 87172 KB Output is correct
2 Correct 4817 ms 87872 KB Output is correct
3 Correct 2 ms 10584 KB Output is correct
4 Correct 2461 ms 86864 KB Output is correct
5 Correct 1584 ms 65436 KB Output is correct
6 Correct 4907 ms 87940 KB Output is correct
7 Correct 4847 ms 87100 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 2 ms 10680 KB Output is correct
10 Correct 5087 ms 87788 KB Output is correct
11 Correct 2530 ms 88512 KB Output is correct
12 Correct 1552 ms 64528 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1422 ms 13088 KB Output is correct
2 Correct 1441 ms 13264 KB Output is correct
3 Correct 1150 ms 13520 KB Output is correct
4 Correct 1037 ms 13432 KB Output is correct
5 Correct 1298 ms 12212 KB Output is correct
6 Correct 9 ms 10788 KB Output is correct
7 Correct 9190 ms 42580 KB Output is correct
8 Correct 8180 ms 42604 KB Output is correct
9 Correct 1036 ms 13428 KB Output is correct
10 Correct 3100 ms 42000 KB Output is correct
11 Correct 3694 ms 41824 KB Output is correct
12 Correct 1420 ms 34532 KB Output is correct
13 Correct 1756 ms 35380 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1422 ms 13088 KB Output is correct
2 Correct 1441 ms 13264 KB Output is correct
3 Correct 1150 ms 13520 KB Output is correct
4 Correct 1037 ms 13432 KB Output is correct
5 Correct 1298 ms 12212 KB Output is correct
6 Correct 9 ms 10788 KB Output is correct
7 Correct 7446 ms 88208 KB Output is correct
8 Correct 7428 ms 88640 KB Output is correct
9 Correct 1105 ms 13188 KB Output is correct
10 Correct 3808 ms 87596 KB Output is correct
11 Correct 4783 ms 88660 KB Output is correct
12 Correct 4860 ms 88028 KB Output is correct
13 Correct 4051 ms 87856 KB Output is correct
14 Correct 4758 ms 87172 KB Output is correct
15 Correct 4817 ms 87872 KB Output is correct
16 Correct 2 ms 10584 KB Output is correct
17 Correct 2461 ms 86864 KB Output is correct
18 Correct 1584 ms 65436 KB Output is correct
19 Correct 4907 ms 87940 KB Output is correct
20 Correct 4847 ms 87100 KB Output is correct
21 Correct 2 ms 10588 KB Output is correct
22 Correct 2 ms 10680 KB Output is correct
23 Correct 5087 ms 87788 KB Output is correct
24 Correct 2530 ms 88512 KB Output is correct
25 Correct 1552 ms 64528 KB Output is correct
26 Correct 9190 ms 42580 KB Output is correct
27 Correct 8180 ms 42604 KB Output is correct
28 Correct 1036 ms 13428 KB Output is correct
29 Correct 3100 ms 42000 KB Output is correct
30 Correct 3694 ms 41824 KB Output is correct
31 Correct 1420 ms 34532 KB Output is correct
32 Correct 1756 ms 35380 KB Output is correct
33 Execution timed out 10034 ms 87928 KB Time limit exceeded
34 Halted 0 ms 0 KB -