oj.uz

답안 #1027912

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1027912 2024-07-19T11:26:11 Z underwaterkillerwhale Road Construction (JOI21_road_construction) C++14
33 / 100
 8034 ms 361616 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) {
        multiset<pair<ll,ll>> 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(a[i].x - a[it->se].x), abs(a[i].y - a[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(0, 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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 95 ms 42660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 359 ms 52140 KB Output is correct
2 Correct 359 ms 52120 KB Output is correct
3 Correct 82 ms 42620 KB Output is correct
4 Correct 278 ms 52028 KB Output is correct
5 Correct 282 ms 52048 KB Output is correct
6 Correct 313 ms 52152 KB Output is correct
7 Correct 266 ms 51504 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 658 ms 79232 KB Output is correct
2 Correct 587 ms 79308 KB Output is correct
3 Correct 17 ms 37976 KB Output is correct
4 Correct 162 ms 77004 KB Output is correct
5 Correct 386 ms 79544 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 658 ms 79232 KB Output is correct
2 Correct 587 ms 79308 KB Output is correct
3 Correct 17 ms 37976 KB Output is correct
4 Correct 162 ms 77004 KB Output is correct
5 Correct 386 ms 79544 KB Output is correct
6 Correct 8034 ms 360916 KB Output is correct
7 Correct 7782 ms 361616 KB Output is correct
8 Correct 5 ms 39392 KB Output is correct
9 Correct 4 ms 39260 KB Output is correct
10 Correct 4740 ms 236596 KB Output is correct
11 Correct 1114 ms 359764 KB Output is correct
12 Correct 4350 ms 330716 KB Output is correct

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 95 ms 42660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 95 ms 42660 KB Output isn't correct
2 Halted 0 ms 0 KB -