oj.uz

Submission #1027916

# Submission time Handle Problem Language Result Execution time Memory
1027916 2024-07-19T11:32:33 Z underwaterkillerwhale Road Construction (JOI21_road_construction) C++14
100 / 100
 8691 ms 355984 KB 
#include <bits/stdc++.h>
#define se              second
#define fs              first
#define mp              make_pair
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)
using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const int N = 3e5 + 7;
const ll Mod = 1e9 + 7;
const int szBL = 916;
const ll INF = 1e12;
const int BASE = 1337;

struct Coor {
    ll x, y;
};

int n, K;
Coor a[N];

namespace sub4 {
     struct Data {
        ll A, B, x;
//        bool operator < (const Data &other) const { return x < other.x; }
    };
    struct Segment_Tree {
        int m;
        pair<ll,int> st[N << 2];

        void init (int n) {
            m = n;
            rep (i, 1, n << 2) st[i] = {INF, -1};
        }
        pair<ll,int> mer(pair<ll,int> A,pair<ll,int> B){ if (A.fs < B.fs) return A; return B;}
        void update (int id, int l, int r, int pos, pair<ll,int> val) {
            if (l > pos || r < pos) return;
            if (l == r) {
                if (st[id].fs > val.fs) st[id] = val;
                return;
            }
            int mid = l + r >> 1;
            update (id<<1,l,mid,pos,val);
            update (id<<1|1,mid+1,r,pos,val);
            st[id]=mer(st[id<<1],st[id<<1|1]);
        }
        pair<ll,int> get (int id,int l,int r, int u,int v) {
            if (l>v||r<u) return {INF, -1};
            if (l>=u&&r<=v) return st[id];
            int mid=l+r>>1;
            return mer(get(id<<1,l,mid,u,v), get(id<<1|1,mid+1,r,u,v));
        }
        void update (int pos,pair<ll,int> val) {
            update (1,1,m,pos,val);
        }
        pair<ll,int> get (int u, int v) {
            return get(1,1,m,u,v);
        }

    }ST1, ST2;

    int numY;
    vector<int> cY;
    bool dd[N];
    map<pair<int,int>, bool> ck;

    void compress () {
        rep (i, 1, n) cY.push_back(a[i].y);
        sort (ALL(cY));
        cY.resize(numY = unique(ALL(cY)) - cY.begin());
    }

    ll Dist (int A, int B) {
        return abs(a[A].x - a[B].x) + abs(a[A].y - a[B].y);
    }
    struct cmp {
        bool operator () (Data A, Data B) { return A.x < B.x || (A.x == B.x && A.A < B.A) || (A.x == B.x && A.A == B.A && A.B < B.B); }
    };
    void addtoset (set<Data, cmp> &cur, int town) {
        if (dd[town]) return;
        rep (i, 1, n) {
            if (i == town) continue;
//            cout << "add: "<<town<<" "<<i<<" "<<Dist(town, i) <<"\n";
            cur.insert({town, i, Dist(town, i)});
        }
    }

    void solution() {
        compress();
        set<Data, cmp> setA;

        rep (k, 1, K) {
            pair<int,int> town;
            ll mnVal = INF;
            ST1.init(numY);
            ST2.init(numY);
            rep (i, 1, n) {
                int pos = lower_bound(ALL(cY), a[i].y) - cY.begin() + 1;
                if (dd[i] == 1) {
                    ST1.update (pos, mp(INF, i));
                    ST2.update (pos, mp(INF, i));
                    continue;
                }
                int B1 = ST1.get (1, pos).se;
                int B2 = ST2.get (pos, numY).se;
                if (B1 != -1 && !dd[B1] && Dist (i, B1) < mnVal) {
                    mnVal = Dist(i, B1);
                    town = {i, B1};
                }
                if (B2 != -1 && !dd[B2] && Dist (i, B2) < mnVal) {
                    mnVal = Dist (i, B2);
                    town = {i, B2};
                }
                ST1.update (pos, mp(-a[i].x - a[i].y, i));
                ST2.update (pos, mp(-a[i].x + a[i].y, i));
            }
            while (!setA.empty()) {
                pair<ll,int> cur = {setA.begin()->A, setA.begin()->B};
                if (ck[cur]) {
                    setA.erase(setA.begin());
                    continue;
                }
                if (Dist (cur.fs, cur.se) < mnVal) {
                    mnVal = Dist (cur.fs, cur.se);
                    town = cur;
                    setA.erase(setA.begin());
                }
                break;
            }
            addtoset(setA, town.fs);
            addtoset(setA, town.se);
            dd[town.fs] = dd[town.se] = 1;
            ck[town] = 1;
            ck[mp(town.se, town.fs)] = 1;
//            cout << town.fs<<" "<<town.se<<" "<<Dist(town.fs, town.se)<<" ";
            cout << mnVal<<"\n";
        }
    }
}

namespace sub5 {
    int m;
    Coor b[N];
    vector<ll> Ans;

    bool check (ll X, int trace) {
        set<pair<ll,int>> S;
        int ptr = 1;
        int res = 0;
        rep (i, 1, n) {
            while (ptr < i && b[ptr].x < b[i].x - X) {
                S.erase(S.find(mp(b[ptr].y, ptr)));
                ++ptr;
            }
            for (auto it = S.lower_bound(mp(b[i].y - X, 0)); it != S.end(); ++it) {
                if (it->fs > b[i].y + X) break;
                if(trace == 0) ++res;
                else if (SZ(Ans) < K) Ans.push_back(max(abs(b[i].x - b[it->se].x), abs(b[i].y - b[it->se].y)));
                if (res == K) return 1;
            }
            S.insert(mp(b[i].y, i));
        }
        return 0;
    }
    void BS (ll L, ll R) {
        while (L < R) {
            ll mid = L + R >> 1;
            if (check(mid, 0)) R = mid;
            else L = mid + 1;
        }
        check(L - 1, 1);
        while (SZ(Ans) < K) Ans.push_back(L);
        sort (ALL(Ans));
        iter (&id, Ans) cout << id <<"\n";
    }
    void solution() {
//        cout << check(3, 4) <<"\n";
        rep (i, 1, n) {
            b[i].x = {a[i].x - a[i].y};
            b[i].y = {a[i].x + a[i].y};
        }
        sort (b + 1, b + 1 + n, [] (Coor A, Coor B) { return A.x < B.x; });
        BS(1, 4e9);

    }
}

void solution () {
    cin >> n >> K;
    rep (i, 1, n) {
        cin >> a[i].x >> a[i].y;
    }
    sort (a + 1, a + 1 + n, [] (Coor A, Coor B) { return A.x < B.x; });
//    rep (i, 1, n) cout <<a[i].x<< ","<<a[i].y<<" ";
//    cout<<"\n";
    if (K <= 10)
        sub4 :: solution();
    else
        sub5 :: solution();

}

#define file(name) freopen(name".inp", "r", stdin); \
//freopen(name".out", "w", stdout);

int main () {
//    file("c");
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll num_Test = 1;
//    cin >> num_Test;
    while(num_Test--)
        solution();
}
/*
nếu mình nghĩ sẽ thay đổi định nghĩa, kiểu dữ liệu của hàm hay mảng j thì mình phải nghĩ xem nó sẽ ảnh hưởng đến các phần nào
5 10
798981764 -961045489
-762214604 -6816243
549909709 362471127
504233152 -881315415
503023672 -79630788
*/

Compilation message

road_construction.cpp: In member function 'void sub4::Segment_Tree::update(int, int, int, int, std::pair<long long int, int>)':
road_construction.cpp:53:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |             int mid = l + r >> 1;
      |                       ~~^~~
road_construction.cpp: In member function 'std::pair<long long int, int> sub4::Segment_Tree::get(int, int, int, int, int)':
road_construction.cpp:61:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |             int mid=l+r>>1;
      |                     ~^~
road_construction.cpp: In function 'void sub5::BS(long long int, long long int)':
road_construction.cpp:178:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  178 |             ll mid = L + R >> 1;
      |                      ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 43964 KB Output is correct
2 Correct 84 ms 43992 KB Output is correct
3 Correct 86 ms 44244 KB Output is correct
4 Correct 76 ms 44252 KB Output is correct
5 Correct 97 ms 42964 KB Output is correct
6 Correct 12 ms 39516 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 49872 KB Output is correct
2 Correct 300 ms 49892 KB Output is correct
3 Correct 83 ms 44000 KB Output is correct
4 Correct 214 ms 48852 KB Output is correct
5 Correct 230 ms 49176 KB Output is correct
6 Correct 223 ms 49128 KB Output is correct
7 Correct 202 ms 48336 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 608 ms 74184 KB Output is correct
2 Correct 580 ms 74188 KB Output is correct
3 Correct 10 ms 37976 KB Output is correct
4 Correct 190 ms 74180 KB Output is correct
5 Correct 399 ms 74040 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 608 ms 74184 KB Output is correct
2 Correct 580 ms 74188 KB Output is correct
3 Correct 10 ms 37976 KB Output is correct
4 Correct 190 ms 74180 KB Output is correct
5 Correct 399 ms 74040 KB Output is correct
6 Correct 8657 ms 355984 KB Output is correct
7 Correct 8691 ms 355940 KB Output is correct
8 Correct 11 ms 37976 KB Output is correct
9 Correct 12 ms 37976 KB Output is correct
10 Correct 5151 ms 230652 KB Output is correct
11 Correct 1198 ms 355944 KB Output is correct
12 Correct 4557 ms 324560 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 43964 KB Output is correct
2 Correct 84 ms 43992 KB Output is correct
3 Correct 86 ms 44244 KB Output is correct
4 Correct 76 ms 44252 KB Output is correct
5 Correct 97 ms 42964 KB Output is correct
6 Correct 12 ms 39516 KB Output is correct
7 Correct 726 ms 47220 KB Output is correct
8 Correct 764 ms 47156 KB Output is correct
9 Correct 88 ms 44160 KB Output is correct
10 Correct 408 ms 46384 KB Output is correct
11 Correct 186 ms 46272 KB Output is correct
12 Correct 497 ms 47364 KB Output is correct
13 Correct 471 ms 45840 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 43964 KB Output is correct
2 Correct 84 ms 43992 KB Output is correct
3 Correct 86 ms 44244 KB Output is correct
4 Correct 76 ms 44252 KB Output is correct
5 Correct 97 ms 42964 KB Output is correct
6 Correct 12 ms 39516 KB Output is correct
7 Correct 279 ms 49872 KB Output is correct
8 Correct 300 ms 49892 KB Output is correct
9 Correct 83 ms 44000 KB Output is correct
10 Correct 214 ms 48852 KB Output is correct
11 Correct 230 ms 49176 KB Output is correct
12 Correct 223 ms 49128 KB Output is correct
13 Correct 202 ms 48336 KB Output is correct
14 Correct 608 ms 74184 KB Output is correct
15 Correct 580 ms 74188 KB Output is correct
16 Correct 10 ms 37976 KB Output is correct
17 Correct 190 ms 74180 KB Output is correct
18 Correct 399 ms 74040 KB Output is correct
19 Correct 8657 ms 355984 KB Output is correct
20 Correct 8691 ms 355940 KB Output is correct
21 Correct 11 ms 37976 KB Output is correct
22 Correct 12 ms 37976 KB Output is correct
23 Correct 5151 ms 230652 KB Output is correct
24 Correct 1198 ms 355944 KB Output is correct
25 Correct 4557 ms 324560 KB Output is correct
26 Correct 726 ms 47220 KB Output is correct
27 Correct 764 ms 47156 KB Output is correct
28 Correct 88 ms 44160 KB Output is correct
29 Correct 408 ms 46384 KB Output is correct
30 Correct 186 ms 46272 KB Output is correct
31 Correct 497 ms 47364 KB Output is correct
32 Correct 471 ms 45840 KB Output is correct
33 Correct 1587 ms 54992 KB Output is correct
34 Correct 1540 ms 55012 KB Output is correct
35 Correct 829 ms 54208 KB Output is correct
36 Correct 845 ms 55080 KB Output is correct
37 Correct 876 ms 55252 KB Output is correct
38 Correct 761 ms 53696 KB Output is correct