oj.uz

Submission #907425

# Submission time Handle Problem Language Result Execution time Memory
907425 2024-01-15T14:09:57 Z lighton Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 126900 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;
        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: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:70:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |         m = l+r>>1;
      |             ~^~
road_construction.cpp: In function 'int main()':
road_construction.cpp:112:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |     scanf("%d %d" , &N,&K);
      |     ~~~~~^~~~~~~~~~~~~~~~~
road_construction.cpp:113:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |     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 1437 ms 13396 KB Output is correct
2 Correct 1446 ms 13688 KB Output is correct
3 Correct 1130 ms 11632 KB Output is correct
4 Correct 1150 ms 11344 KB Output is correct
5 Correct 1289 ms 12532 KB Output is correct
6 Correct 11 ms 10840 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7450 ms 126176 KB Output is correct
2 Correct 7572 ms 125756 KB Output is correct
3 Correct 1057 ms 11336 KB Output is correct
4 Correct 3917 ms 126080 KB Output is correct
5 Correct 4803 ms 126864 KB Output is correct
6 Correct 4845 ms 125824 KB Output is correct
7 Correct 4189 ms 125836 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4886 ms 125320 KB Output is correct
2 Correct 4845 ms 126076 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2438 ms 125436 KB Output is correct
5 Correct 1873 ms 125188 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4886 ms 125320 KB Output is correct
2 Correct 4845 ms 126076 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2438 ms 125436 KB Output is correct
5 Correct 1873 ms 125188 KB Output is correct
6 Correct 4843 ms 126044 KB Output is correct
7 Correct 4926 ms 126900 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 4698 ms 126604 KB Output is correct
11 Correct 2467 ms 125920 KB Output is correct
12 Correct 1867 ms 125576 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1437 ms 13396 KB Output is correct
2 Correct 1446 ms 13688 KB Output is correct
3 Correct 1130 ms 11632 KB Output is correct
4 Correct 1150 ms 11344 KB Output is correct
5 Correct 1289 ms 12532 KB Output is correct
6 Correct 11 ms 10840 KB Output is correct
7 Correct 8219 ms 46572 KB Output is correct
8 Correct 8180 ms 45400 KB Output is correct
9 Correct 1142 ms 11348 KB Output is correct
10 Correct 3208 ms 45736 KB Output is correct
11 Correct 3654 ms 45112 KB Output is correct
12 Correct 1791 ms 46920 KB Output is correct
13 Correct 2081 ms 44952 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1437 ms 13396 KB Output is correct
2 Correct 1446 ms 13688 KB Output is correct
3 Correct 1130 ms 11632 KB Output is correct
4 Correct 1150 ms 11344 KB Output is correct
5 Correct 1289 ms 12532 KB Output is correct
6 Correct 11 ms 10840 KB Output is correct
7 Correct 7450 ms 126176 KB Output is correct
8 Correct 7572 ms 125756 KB Output is correct
9 Correct 1057 ms 11336 KB Output is correct
10 Correct 3917 ms 126080 KB Output is correct
11 Correct 4803 ms 126864 KB Output is correct
12 Correct 4845 ms 125824 KB Output is correct
13 Correct 4189 ms 125836 KB Output is correct
14 Correct 4886 ms 125320 KB Output is correct
15 Correct 4845 ms 126076 KB Output is correct
16 Correct 2 ms 8540 KB Output is correct
17 Correct 2438 ms 125436 KB Output is correct
18 Correct 1873 ms 125188 KB Output is correct
19 Correct 4843 ms 126044 KB Output is correct
20 Correct 4926 ms 126900 KB Output is correct
21 Correct 2 ms 8540 KB Output is correct
22 Correct 2 ms 8540 KB Output is correct
23 Correct 4698 ms 126604 KB Output is correct
24 Correct 2467 ms 125920 KB Output is correct
25 Correct 1867 ms 125576 KB Output is correct
26 Correct 8219 ms 46572 KB Output is correct
27 Correct 8180 ms 45400 KB Output is correct
28 Correct 1142 ms 11348 KB Output is correct
29 Correct 3208 ms 45736 KB Output is correct
30 Correct 3654 ms 45112 KB Output is correct
31 Correct 1791 ms 46920 KB Output is correct
32 Correct 2081 ms 44952 KB Output is correct
33 Execution timed out 10073 ms 125164 KB Time limit exceeded
34 Halted 0 ms 0 KB -