oj.uz

Submission #1027975

# Submission time Handle Problem Language Result Execution time Memory
1027975 2024-07-19T12:07:26 Z underwaterkillerwhale Road Construction (JOI21_road_construction) C++14
100 / 100
 2243 ms 241360 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;

    struct cmp {
        bool operator () (Data A, Data B) { return A.x > B.x; }
    };

    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);
    }

    void addtoset (priority_queue<Data, vector<Data>, cmp> &cur, int town, int pvc) {
        if (dd[town]) return;
        rep (i, 1, n) {
            if (i == town || i == pvc) continue;
            if (dd[i])
                continue;
            cur.push({town, i, Dist(town, i)});
        }
    }

    void solution() {
        compress();
        priority_queue<Data, vector<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 + 1, i));
                    ST2.update (pos, mp(INF + 1, i));
                    continue;
                }
                int B1 = ST1.get (1, pos).se;
                int B2 = ST2.get (pos, numY).se;
                if (B1 != -1 && Dist (i, B1) < mnVal) {
                    mnVal = Dist(i, B1);
                    town = {i, B1};
                }
                if (B2 != -1 && 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));
            }
            if (!setA.empty()) {
                pair<int,int> cur = {setA.top().A, setA.top().B};
                if (Dist (cur.fs, cur.se) < mnVal) {
                    mnVal = Dist (cur.fs, cur.se);
                    town = cur;
                    setA.pop();
                }
            }
            addtoset(setA, town.fs, town.se);
            addtoset(setA, town.se, town.fs);
            dd[town.fs] = dd[town.se] = 1;
            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);

    }
}
//
//namespace sub2 {
//    void solution() {
//        priorit
//    }
//}

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 (sub2 :: check())
//        sub2 :: solution();
//    else
        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:173:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  173 |             ll mid = L + R >> 1;
      |                      ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 43964 KB Output is correct
2 Correct 76 ms 43988 KB Output is correct
3 Correct 71 ms 44244 KB Output is correct
4 Correct 80 ms 44244 KB Output is correct
5 Correct 71 ms 42960 KB Output is correct
6 Correct 7 ms 39400 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 50236 KB Output is correct
2 Correct 236 ms 50096 KB Output is correct
3 Correct 63 ms 44012 KB Output is correct
4 Correct 190 ms 49880 KB Output is correct
5 Correct 174 ms 50148 KB Output is correct
6 Correct 173 ms 50148 KB Output is correct
7 Correct 161 ms 49364 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 56764 KB Output is correct
2 Correct 301 ms 57792 KB Output is correct
3 Correct 4 ms 39260 KB Output is correct
4 Correct 74 ms 57232 KB Output is correct
5 Correct 123 ms 57992 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 56764 KB Output is correct
2 Correct 301 ms 57792 KB Output is correct
3 Correct 4 ms 39260 KB Output is correct
4 Correct 74 ms 57232 KB Output is correct
5 Correct 123 ms 57992 KB Output is correct
6 Correct 2243 ms 241212 KB Output is correct
7 Correct 2232 ms 241216 KB Output is correct
8 Correct 4 ms 39256 KB Output is correct
9 Correct 4 ms 39260 KB Output is correct
10 Correct 2087 ms 142828 KB Output is correct
11 Correct 288 ms 241360 KB Output is correct
12 Correct 760 ms 241208 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 43964 KB Output is correct
2 Correct 76 ms 43988 KB Output is correct
3 Correct 71 ms 44244 KB Output is correct
4 Correct 80 ms 44244 KB Output is correct
5 Correct 71 ms 42960 KB Output is correct
6 Correct 7 ms 39400 KB Output is correct
7 Correct 663 ms 47828 KB Output is correct
8 Correct 651 ms 47824 KB Output is correct
9 Correct 68 ms 44252 KB Output is correct
10 Correct 385 ms 47076 KB Output is correct
11 Correct 164 ms 46936 KB Output is correct
12 Correct 443 ms 47888 KB Output is correct
13 Correct 429 ms 46272 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 43964 KB Output is correct
2 Correct 76 ms 43988 KB Output is correct
3 Correct 71 ms 44244 KB Output is correct
4 Correct 80 ms 44244 KB Output is correct
5 Correct 71 ms 42960 KB Output is correct
6 Correct 7 ms 39400 KB Output is correct
7 Correct 234 ms 50236 KB Output is correct
8 Correct 236 ms 50096 KB Output is correct
9 Correct 63 ms 44012 KB Output is correct
10 Correct 190 ms 49880 KB Output is correct
11 Correct 174 ms 50148 KB Output is correct
12 Correct 173 ms 50148 KB Output is correct
13 Correct 161 ms 49364 KB Output is correct
14 Correct 287 ms 56764 KB Output is correct
15 Correct 301 ms 57792 KB Output is correct
16 Correct 4 ms 39260 KB Output is correct
17 Correct 74 ms 57232 KB Output is correct
18 Correct 123 ms 57992 KB Output is correct
19 Correct 2243 ms 241212 KB Output is correct
20 Correct 2232 ms 241216 KB Output is correct
21 Correct 4 ms 39256 KB Output is correct
22 Correct 4 ms 39260 KB Output is correct
23 Correct 2087 ms 142828 KB Output is correct
24 Correct 288 ms 241360 KB Output is correct
25 Correct 760 ms 241208 KB Output is correct
26 Correct 663 ms 47828 KB Output is correct
27 Correct 651 ms 47824 KB Output is correct
28 Correct 68 ms 44252 KB Output is correct
29 Correct 385 ms 47076 KB Output is correct
30 Correct 164 ms 46936 KB Output is correct
31 Correct 443 ms 47888 KB Output is correct
32 Correct 429 ms 46272 KB Output is correct
33 Correct 1380 ms 51136 KB Output is correct
34 Correct 1412 ms 50932 KB Output is correct
35 Correct 759 ms 50112 KB Output is correct
36 Correct 756 ms 50884 KB Output is correct
37 Correct 798 ms 51176 KB Output is correct
38 Correct 688 ms 49344 KB Output is correct