oj.uz

Submission #1027444

# Submission time Handle Problem Language Result Execution time Memory
1027444 2024-07-19T06:29:47 Z underwaterkillerwhale Road Construction (JOI21_road_construction) C++14
27 / 100
 7942 ms 361092 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";
        }
    }
}

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 39256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 42004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 74444 KB Output is correct
2 Correct 495 ms 74188 KB Output is correct
3 Correct 6 ms 39256 KB Output is correct
4 Correct 156 ms 77260 KB Output is correct
5 Correct 387 ms 79508 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 74444 KB Output is correct
2 Correct 495 ms 74188 KB Output is correct
3 Correct 6 ms 39256 KB Output is correct
4 Correct 156 ms 77260 KB Output is correct
5 Correct 387 ms 79508 KB Output is correct
6 Correct 7942 ms 361092 KB Output is correct
7 Correct 7873 ms 361056 KB Output is correct
8 Correct 7 ms 39260 KB Output is correct
9 Correct 7 ms 39260 KB Output is correct
10 Correct 4870 ms 235844 KB Output is correct
11 Correct 1242 ms 359120 KB Output is correct
12 Correct 4426 ms 330084 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 39256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 39256 KB Output isn't correct
2 Halted 0 ms 0 KB -