oj.uz

Submission #397178

# Submission time Handle Problem Language Result Execution time Memory
397178 2021-05-01T16:45:22 Z 12tqian Road Construction (JOI21_road_construction) C++17
100 / 100
 4209 ms 676112 KB 
#include <bits/stdc++.h>

using namespace std;

#define f1r(i, a, b) for (int i = a; i < b; ++i)
#define f0r(i, a) f1r(i, 0, a)
#define each(t, a) for (auto& t : a)

#define mp make_pair
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

template <class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

const int M = 4e7;
const int INF = 2e9 + 7;

struct Node {
    int lc, rc;
    int mx = -INF;
    int loc = -INF;
} t[M];

int cnt = 0;

int modify(int p, int l, int r, int x, int v) {
    int u = ++cnt;
    if (l == r) {
        t[u].mx = v;
        t[u].loc = l;
    } else {
        int m = (l + r) >> 1;
        if (x <= m) {
            t[u].lc = modify(t[p].lc, l, m, x, v);
            t[u].rc = t[p].rc;
        } else {
            t[u].lc = t[p].lc;
            t[u].rc = modify(t[p].rc, m + 1, r, x, v);
        }
        int L = t[t[u].lc].mx;
        int R = t[t[u].rc].mx;
        if (L > R) {
            t[u].mx = L;
            t[u].loc = t[t[u].lc].loc;
        } else {
            t[u].mx = R;            
            t[u].loc = t[t[u].rc].loc;
        }
    }
    return u;
}

pi query(int p, int l, int r, int lo, int hi) {
    if (hi < l || r < lo) return {-INF, -INF};;
    if (lo <= l && r <= hi) return {t[p].mx, t[p].loc};
    int m = (l + r) >> 1;
    return max(query(t[p].lc, l, m, lo, hi), query(t[p].rc, m + 1, r ,lo, hi));
}

int new_node() {
    ++cnt;
    t[cnt].lc = t[cnt].rc = cnt;
    t[cnt].mx = -INF;
    t[cnt].loc = -INF;
    return cnt;
}

template <class T> int get_pos(vector<T>& v, T x) {
    return lower_bound(all(v), x) - v.begin();
}

void reset() {
    f0r(i, cnt + 1) {
        t[i].lc = t[i].rc = 0;
        t[i].mx = t[i].loc = -INF;
    }
    cnt = 0;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    
    int n, k; cin >> n >> k;
   
    vpi pts(n);
   
    f0r(i, n) {
        cin >> pts[i].f >> pts[i].s;
    }
   
    vi xvals;
    vi yvals;

    typedef pair<ll, int> T;

    priority_queue<T, vector<T>, greater<T>> pq;

    vl dists;
   
    { // diagonally up, not equal x or y
        reset();
        while (!pq.empty()) pq.pop();
        xvals.clear();
        yvals.clear();
        
        sort(all(pts));
        
        f0r(i, n) {
            xvals.pb(pts[i].f);
            yvals.pb(pts[i].s);
        }
        
        xvals.pb(-INF);
        yvals.pb(-INF);
        
        sort(all(xvals));
        sort(all(yvals));
        
        xvals.erase(unique(all(xvals)), xvals.end());
        yvals.erase(unique(all(yvals)), yvals.end());

        int nx = sz(xvals);
        int ny = sz(yvals);

        vector<vi> by_x(nx);
        vector<vi> by_y(ny);

        each(p, pts) {
            by_x[get_pos(xvals, p.f)].pb(p.s);
            by_y[get_pos(yvals, p.s)].pb(p.f);
        }

        each(y, by_y) sort(all(y));

        vi seg(n); // corresponding segtree for each point
       
        int rec = new_node();
       
        f0r(i, nx) { // iterate over xvals
            each(p, by_x[i]) { // this is before for exclusive
                int x = xvals[i];
                int y = p;
                int pid = get_pos(pts, mp(x, y));
                seg[pid] = rec;
            }
            each(p, by_x[i]) {
                int x = xvals[i];
                int y = p;
                int id = get_pos(yvals, y);
                rec = modify(rec, 0, ny - 1, id, x + y);
            }
        }
        
        auto add = [&](int i) {
            int x = pts[i].f;
            int y = pts[i].s;
            int yid = get_pos(yvals, y);
            
            auto res = query(seg[i], 0, ny - 1, 0, yid - 1); // check next point
            
            if (res.f == -INF) return;
            
            ll dist = 0LL + x + y - res.f;

            pq.push(mp(dist, i));  
        };

        auto nullify = [&](int i) {
            int x = pts[i].f;
            int y = pts[i].s;
            int yid = get_pos(yvals, y);

            auto res = query(seg[i], 0, ny - 1, 0, yid - 1); // exclusive

            assert(res.f != -INF);

            int loc = res.s;

            int xloc = res.f - yvals[loc]; 

            int xid = get_pos(by_y[loc], xloc);

            if (xid == 0) {
                seg[i] = modify(seg[i], 0, ny - 1, loc, -INF); // set to null
            } else {                
                seg[i] = modify(seg[i], 0, ny - 1, loc, yvals[loc] + by_y[loc][xid - 1]); // set to null
            }
        };
        
        f0r(i, n) {
            int x = pts[i].f;
            int y = pts[i].s;
            int yid = get_pos(yvals, y);
            
            auto res = query(seg[i], 0, ny - 1, 0, yid - 1); // exclusive

            if (res.f == -INF) continue;
            
            ll dist = 0LL + x + y - res.f;
            dists.pb(dist); // initial dist
            
            nullify(i);
            add(i);
        }
        
        int t = 0;
        
        while (t < k && !pq.empty()) {
            auto top = pq.top();
            pq.pop();
            dists.pb(top.f);
            
            int i = top.s;

            nullify(i);
            add(i);            

            t++;
        }
    }
    { // possibly equal x, y
        reset();
        while (!pq.empty()) pq.pop();
        xvals.clear();
        yvals.clear();

        f0r(i, n) pts[i].f *= -1;
        
        sort(all(pts));
        
        f0r(i, n) {
            xvals.pb(pts[i].f);
            yvals.pb(pts[i].s);
        }
        
        xvals.pb(-INF);
        yvals.pb(-INF);
        
        sort(all(xvals));
        sort(all(yvals));
        
        xvals.erase(unique(all(xvals)), xvals.end());
        yvals.erase(unique(all(yvals)), yvals.end());

        int nx = sz(xvals);
        int ny = sz(yvals);

        vector<vi> by_x(nx);
        vector<vi> by_y(ny);

        each(p, pts) {
            by_x[get_pos(xvals, p.f)].pb(p.s);
            by_y[get_pos(yvals, p.s)].pb(p.f);
        }

        each(y, by_y) sort(all(y));

        vi seg(n); // corresponding segtree for each point
       
        int rec = new_node();
       
        f0r(i, nx) { // iterate over xvals
            each(p, by_x[i]) {
                int x = xvals[i];
                int y = p;
                int id = get_pos(yvals, y);
                rec = modify(rec, 0, ny - 1, id, x + y);
            }
         
            each(p, by_x[i]) { // this is before for exclusive
                int x = xvals[i];
                int y = p;
                int pid = get_pos(pts, mp(x, y));
                seg[pid] = rec;
            }
        }

        auto add = [&](int i) {
            int x = pts[i].f;
            int y = pts[i].s;
            int yid = get_pos(yvals, y);
            
            auto res = query(seg[i], 0, ny - 1, 0, yid); // check next point
            
            if (res.f == -INF) return;
            
            ll dist = 0LL + x + y - res.f;

            pq.push(mp(dist, i));  
        };

        auto nullify = [&](int i) {
            int x = pts[i].f;
            int y = pts[i].s;
            int yid = get_pos(yvals, y);

            auto res = query(seg[i], 0, ny - 1, 0, yid); 

            assert(res.f != -INF);

            int loc = res.s;

            int xloc = res.f - yvals[loc]; 

            int xid = get_pos(by_y[loc], xloc);

            if (xid == 0) {
                seg[i] = modify(seg[i], 0, ny - 1, loc, -INF); // set to null
            } else {                
                seg[i] = modify(seg[i], 0, ny - 1, loc, yvals[loc] + by_y[loc][xid - 1]); // set to null
            }
        };
        
        f0r(i, n) { 
            int x = pts[i].f;
            int y = pts[i].s;
            int yid = get_pos(yvals, y);
            
            auto res = query(seg[i], 0, ny - 1, 0, yid); // exclusive

            if (res.f == -INF) continue;
            
            int loc = res.s;

            ll dist = 0LL + x + y - res.f;
            
            assert(dist == 0);

            nullify(i);
            add(i);
        }
        
        int t = 0;
        
        while (t < k && !pq.empty()) {
            auto top = pq.top();
            pq.pop();
            dists.pb(top.f);
            
            int i = top.s;

            nullify(i);
            add(i);            

            t++;
        }
    }

    sort(all(dists));

    f0r(i, k) {
        cout << dists[i] << '\n';
    }
    return 0;
}

/**
 * we have to pursue from a few directions
 * can have equal y coordinate, but not x coordinate
 * 
 */

Compilation message

road_construction.cpp: In lambda function:
road_construction.cpp:182:17: warning: unused variable 'x' [-Wunused-variable]
  182 |             int x = pts[i].f;
      |                 ^
road_construction.cpp: In lambda function:
road_construction.cpp:306:17: warning: unused variable 'x' [-Wunused-variable]
  306 |             int x = pts[i].f;
      |                 ^
road_construction.cpp: In function 'int main()':
road_construction.cpp:336:17: warning: unused variable 'loc' [-Wunused-variable]
  336 |             int loc = res.s;
      |                 ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 898 ms 633324 KB Output is correct
2 Correct 860 ms 633324 KB Output is correct
3 Correct 550 ms 631344 KB Output is correct
4 Correct 509 ms 631512 KB Output is correct
5 Correct 682 ms 632232 KB Output is correct
6 Correct 311 ms 626676 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 810 ms 660348 KB Output is correct
2 Correct 791 ms 660348 KB Output is correct
3 Correct 402 ms 631176 KB Output is correct
4 Correct 684 ms 660144 KB Output is correct
5 Correct 660 ms 660296 KB Output is correct
6 Correct 666 ms 660476 KB Output is correct
7 Correct 668 ms 659728 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2427 ms 670044 KB Output is correct
2 Correct 2419 ms 670000 KB Output is correct
3 Correct 313 ms 626500 KB Output is correct
4 Correct 583 ms 656916 KB Output is correct
5 Correct 933 ms 644856 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2427 ms 670044 KB Output is correct
2 Correct 2419 ms 670000 KB Output is correct
3 Correct 313 ms 626500 KB Output is correct
4 Correct 583 ms 656916 KB Output is correct
5 Correct 933 ms 644856 KB Output is correct
6 Correct 2369 ms 670056 KB Output is correct
7 Correct 2427 ms 670112 KB Output is correct
8 Correct 304 ms 626500 KB Output is correct
9 Correct 305 ms 626488 KB Output is correct
10 Correct 2359 ms 666740 KB Output is correct
11 Correct 583 ms 656980 KB Output is correct
12 Correct 928 ms 644752 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 898 ms 633324 KB Output is correct
2 Correct 860 ms 633324 KB Output is correct
3 Correct 550 ms 631344 KB Output is correct
4 Correct 509 ms 631512 KB Output is correct
5 Correct 682 ms 632232 KB Output is correct
6 Correct 311 ms 626676 KB Output is correct
7 Correct 2557 ms 651368 KB Output is correct
8 Correct 2545 ms 651256 KB Output is correct
9 Correct 505 ms 631468 KB Output is correct
10 Correct 2056 ms 649164 KB Output is correct
11 Correct 1936 ms 648392 KB Output is correct
12 Correct 885 ms 641912 KB Output is correct
13 Correct 875 ms 641380 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 898 ms 633324 KB Output is correct
2 Correct 860 ms 633324 KB Output is correct
3 Correct 550 ms 631344 KB Output is correct
4 Correct 509 ms 631512 KB Output is correct
5 Correct 682 ms 632232 KB Output is correct
6 Correct 311 ms 626676 KB Output is correct
7 Correct 810 ms 660348 KB Output is correct
8 Correct 791 ms 660348 KB Output is correct
9 Correct 402 ms 631176 KB Output is correct
10 Correct 684 ms 660144 KB Output is correct
11 Correct 660 ms 660296 KB Output is correct
12 Correct 666 ms 660476 KB Output is correct
13 Correct 668 ms 659728 KB Output is correct
14 Correct 2427 ms 670044 KB Output is correct
15 Correct 2419 ms 670000 KB Output is correct
16 Correct 313 ms 626500 KB Output is correct
17 Correct 583 ms 656916 KB Output is correct
18 Correct 933 ms 644856 KB Output is correct
19 Correct 2369 ms 670056 KB Output is correct
20 Correct 2427 ms 670112 KB Output is correct
21 Correct 304 ms 626500 KB Output is correct
22 Correct 305 ms 626488 KB Output is correct
23 Correct 2359 ms 666740 KB Output is correct
24 Correct 583 ms 656980 KB Output is correct
25 Correct 928 ms 644752 KB Output is correct
26 Correct 2557 ms 651368 KB Output is correct
27 Correct 2545 ms 651256 KB Output is correct
28 Correct 505 ms 631468 KB Output is correct
29 Correct 2056 ms 649164 KB Output is correct
30 Correct 1936 ms 648392 KB Output is correct
31 Correct 885 ms 641912 KB Output is correct
32 Correct 875 ms 641380 KB Output is correct
33 Correct 4209 ms 675944 KB Output is correct
34 Correct 4141 ms 676112 KB Output is correct
35 Correct 3530 ms 666644 KB Output is correct
36 Correct 1331 ms 651612 KB Output is correct
37 Correct 1350 ms 651332 KB Output is correct
38 Correct 1335 ms 652404 KB Output is correct