oj.uz

Submission #907411

# Submission time Handle Problem Language Result Execution time Memory
907411 2024-01-15T13:51:21 Z lighton Road Construction (JOI21_road_construction) C++17
0 / 100
 10000 ms 126800 KB 
#include <bits/stdc++.h>
#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(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,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 count){
    ll l = 0;
    ll r = inf;
    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 xs = LB(x,xl) + 1;
        int xe = UB(x+m,xl)-1 + 1;
        int tmp = pst.query(pst.root[xe],pst.root[xs-1],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(X[i],Y[i],cnt[i]+1) , i});
        cnt[i]++;
    }
    forf(trash,1,K) {
        printf("%lld\n", -pq.top().first);
        int i  = pq.top().second;
        pq.pop();
        pq.push({-findmin(X[i],Y[i],cnt[i]+1) , 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:33:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |         int m = s+e>>1;
      |                 ~^~
road_construction.cpp: In member function 'int PST::query(int, int, int, int, int, int)':
road_construction.cpp:49:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |         int m = s+e>>1;
      |                 ~^~
road_construction.cpp: In function 'll findmin(ll, ll, int)':
road_construction.cpp:66:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |         m = l+r>>1;
      |             ~^~
road_construction.cpp: In function 'int main()':
road_construction.cpp:110:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |     scanf("%d %d" , &N,&K);
      |     ~~~~~^~~~~~~~~~~~~~~~~
road_construction.cpp:111:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |     forf(i,1,N) scanf("%lld %lld" , &X[i] , &Y[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1772 ms 11508 KB Output is correct
2 Correct 1770 ms 11552 KB Output is correct
3 Correct 1529 ms 11412 KB Output is correct
4 Correct 1940 ms 11328 KB Output is correct
5 Incorrect 2173 ms 10484 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10087 ms 124888 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10089 ms 126800 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10089 ms 126800 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1772 ms 11508 KB Output is correct
2 Correct 1770 ms 11552 KB Output is correct
3 Correct 1529 ms 11412 KB Output is correct
4 Correct 1940 ms 11328 KB Output is correct
5 Incorrect 2173 ms 10484 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1772 ms 11508 KB Output is correct
2 Correct 1770 ms 11552 KB Output is correct
3 Correct 1529 ms 11412 KB Output is correct
4 Correct 1940 ms 11328 KB Output is correct
5 Incorrect 2173 ms 10484 KB Output isn't correct
6 Halted 0 ms 0 KB -