oj.uz

답안 #1027451

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1027451 2024-07-19T06:39:08 Z underwaterkillerwhale Road Construction (JOI21_road_construction) C++14
27 / 100
 8597 ms 360904 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);
    }

    void addtoset (set<array<ll, 3>> &cur, int town) {
        if (dd[town]) return;
        rep (i, 1, n) {
            if (i == town) continue;
            cur.insert({ Dist(town, i), town, i});
        }
    }

    void solution() {
        compress();
        set<array<ll, 3>> 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()) {
                array<ll, 3> curA = *setA.begin();
                pair<ll,int> cur = {curA[1], curA[2]};
                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] = ck[mp(town.se, town.fs)] = 1;
            cout << mnVal<<"\n";
        }
    }
}

namespace sub5 {

}

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

    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;
      |                     ~^~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 6.0

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

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 549 ms 79112 KB Output is correct
2 Correct 514 ms 79312 KB Output is correct
3 Correct 13 ms 37980 KB Output is correct
4 Correct 176 ms 77092 KB Output is correct
5 Correct 367 ms 79296 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 549 ms 79112 KB Output is correct
2 Correct 514 ms 79312 KB Output is correct
3 Correct 13 ms 37980 KB Output is correct
4 Correct 176 ms 77092 KB Output is correct
5 Correct 367 ms 79296 KB Output is correct
6 Correct 8597 ms 360856 KB Output is correct
7 Correct 7862 ms 360904 KB Output is correct
8 Correct 13 ms 37976 KB Output is correct
9 Correct 16 ms 37980 KB Output is correct
10 Correct 5498 ms 235436 KB Output is correct
11 Correct 1163 ms 358740 KB Output is correct
12 Correct 4393 ms 329632 KB Output is correct

Subtask #5
0 / 27.0

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

Subtask #6
0 / 35.0

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