oj.uz

Submission #907426

# Submission time Handle Problem Language Result Execution time Memory
907426 2024-01-15T14:15:09 Z lighton Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 126668 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;
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 query(int now ,int prv, int s, int e, int l ,int r){
        //if(r<l) return 0;
        if(l<=s && e<=r) return node[now].val-node[prv].val;
        if(s>r || e<l) return 0;
        if(node[now].val == 0 && node[prv].val == 0) return 0;
        int m = s+e>>1;
        return query(node[now].l,node[prv].l,s,m,l,r)+query(node[now].r,node[prv].r,m+1,e,l,r);
    }
} 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,N,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;
    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;
        int tmp = pst.query(pst.root[xe],pst.root[xs],1,N,ys,ye);
        if(tmp >= count) r=m;
        else l=m;
    }
    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);
    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, 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:71:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |         m = l+r>>1;
      |             ~^~
road_construction.cpp: In function 'int main()':
road_construction.cpp:113:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |     scanf("%d %d" , &N,&K);
      |     ~~~~~^~~~~~~~~~~~~~~~~
road_construction.cpp:114:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |     forf(i,1,N) scanf("%lld %lld" , &X[i] , &Y[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1444 ms 13636 KB Output is correct
2 Correct 1431 ms 13588 KB Output is correct
3 Correct 1147 ms 11344 KB Output is correct
4 Correct 1186 ms 11600 KB Output is correct
5 Correct 1344 ms 12304 KB Output is correct
6 Correct 10 ms 10844 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7801 ms 126192 KB Output is correct
2 Correct 7936 ms 125072 KB Output is correct
3 Correct 1110 ms 11328 KB Output is correct
4 Correct 4090 ms 125572 KB Output is correct
5 Correct 5066 ms 125320 KB Output is correct
6 Correct 5041 ms 125324 KB Output is correct
7 Correct 4361 ms 125432 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5108 ms 126428 KB Output is correct
2 Correct 4999 ms 126180 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2524 ms 125076 KB Output is correct
5 Correct 1895 ms 125180 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5108 ms 126428 KB Output is correct
2 Correct 4999 ms 126180 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2524 ms 125076 KB Output is correct
5 Correct 1895 ms 125180 KB Output is correct
6 Correct 5038 ms 126668 KB Output is correct
7 Correct 5141 ms 126348 KB Output is correct
8 Correct 2 ms 8536 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 4993 ms 126416 KB Output is correct
11 Correct 2541 ms 125036 KB Output is correct
12 Correct 1898 ms 125068 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1444 ms 13636 KB Output is correct
2 Correct 1431 ms 13588 KB Output is correct
3 Correct 1147 ms 11344 KB Output is correct
4 Correct 1186 ms 11600 KB Output is correct
5 Correct 1344 ms 12304 KB Output is correct
6 Correct 10 ms 10844 KB Output is correct
7 Correct 8585 ms 46744 KB Output is correct
8 Correct 8488 ms 46424 KB Output is correct
9 Correct 1186 ms 11348 KB Output is correct
10 Correct 3356 ms 46188 KB Output is correct
11 Correct 3841 ms 45288 KB Output is correct
12 Correct 1824 ms 45736 KB Output is correct
13 Correct 2174 ms 45288 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1444 ms 13636 KB Output is correct
2 Correct 1431 ms 13588 KB Output is correct
3 Correct 1147 ms 11344 KB Output is correct
4 Correct 1186 ms 11600 KB Output is correct
5 Correct 1344 ms 12304 KB Output is correct
6 Correct 10 ms 10844 KB Output is correct
7 Correct 7801 ms 126192 KB Output is correct
8 Correct 7936 ms 125072 KB Output is correct
9 Correct 1110 ms 11328 KB Output is correct
10 Correct 4090 ms 125572 KB Output is correct
11 Correct 5066 ms 125320 KB Output is correct
12 Correct 5041 ms 125324 KB Output is correct
13 Correct 4361 ms 125432 KB Output is correct
14 Correct 5108 ms 126428 KB Output is correct
15 Correct 4999 ms 126180 KB Output is correct
16 Correct 2 ms 8540 KB Output is correct
17 Correct 2524 ms 125076 KB Output is correct
18 Correct 1895 ms 125180 KB Output is correct
19 Correct 5038 ms 126668 KB Output is correct
20 Correct 5141 ms 126348 KB Output is correct
21 Correct 2 ms 8536 KB Output is correct
22 Correct 2 ms 8540 KB Output is correct
23 Correct 4993 ms 126416 KB Output is correct
24 Correct 2541 ms 125036 KB Output is correct
25 Correct 1898 ms 125068 KB Output is correct
26 Correct 8585 ms 46744 KB Output is correct
27 Correct 8488 ms 46424 KB Output is correct
28 Correct 1186 ms 11348 KB Output is correct
29 Correct 3356 ms 46188 KB Output is correct
30 Correct 3841 ms 45288 KB Output is correct
31 Correct 1824 ms 45736 KB Output is correct
32 Correct 2174 ms 45288 KB Output is correct
33 Execution timed out 10022 ms 126180 KB Time limit exceeded
34 Halted 0 ms 0 KB -