Submission #1288684

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288684		adscoding	Road Construction (JOI21_road_construction)	C++20	100 / 100	1850 ms	1191488 KiB

road_construction

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define BIT(mask, x) ((mask >> (x)) & 1)
#define FOR(i, a, b) for (int i = a, _b = b; i <= _b; ++i)
#define FORD(i, a, b) for (int i = a, _b = b; i >= _b; --i)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define dbg(...) cerr << "[" << #__VA_ARGS__ << "] = ", debug(__VA_ARGS__)
template<typename T> void debug(T x) { cerr << x << "\n"; }
template<typename T, typename... Args> void debug(T x, Args... args) {
    cerr << x << ", "; debug(args...);
}


// -------------------------------------- CON CUA BO HCN --------------------------------------

const int maxn = 2.5e5 + 3;
int n, K, id[maxn], m;
pll a[maxn];
pll ids[maxn];

// --------------------------------------------------------------------------------------------

struct Node
{
    int l, r; pll val;
    Node() {l = r = 0; val.first = val.second = 1e18;}
};

struct PerSeg
{
    vector<Node> seg; int curNode;
    vector<int> root;
    void init(int _n) {seg.resize(100 * max(_n, K)); root.assign(n + 1, 0); curNode = 0;}
    void upd(int id, int l, int r, int pos, ll val)
    {
        if (l == r)
        {
            return void(seg[id].val = {val, l});
        }
        int mid = l + r >> 1;

        if (pos <= mid)
        {
            seg[++curNode] = seg[seg[id].l];
            seg[id].l = curNode;
            upd(curNode, l, mid, pos, val);
        }
        else
        {
            seg[++curNode] = seg[seg[id].r];
            seg[id].r = curNode;
            upd(curNode, mid + 1, r, pos, val);
        }

        seg[id].val = min(seg[seg[id].l].val, seg[seg[id].r].val);
    }

    pll get(int id, int l, int r, int u, int v)
    {
        if (l > r || l > v || r < u) return {ll(1e18), ll(1e18)};
        if (l >= u && r <= v) return seg[id].val;
        int mid = l + r >> 1 ;
        return min(get(seg[id].l, l, mid, u, v), get(seg[id].r, mid + 1, r, u, v));
    }
} segLowerL, segLowerR;


ll get_ans(const int &pos)
{
    pll x = segLowerL.get(segLowerL.root[pos], 1, m, 1, id[pos]); 
    pll y = segLowerR.get(segLowerR.root[pos], 1, m, id[pos] + 1, m); 

    if (x.first == 1e18 && y.first == 1e18) return 1e18;

    // if (x.first < 0) 

    x.first += a[pos].first + a[pos].second;
    y.first += a[pos].first - a[pos].second;
    // dbg(pos);
    // dbg(x.first, x.second);
    // dbg(y.first, y.second);
    if (x.first <= y.first)
    {
        segLowerL.upd(segLowerL.root[pos], 1, m, x.second, 1e18);
        return x.first;
    }
    segLowerR.upd(segLowerR.root[pos], 1, m, y.second, 1e18);
    return y.first;
}

void solve()
{
    cin >> n >> K;
    FOR(i, 1, n) cin >> a[i].first >> a[i].second;
    sort(a + 1, a + n + 1);
    FOR(i, 1, n) ids[i] = {a[i].second, i};
    
    sort(ids + 1, ids + n + 1);

    m = n;
    segLowerL.init(m); segLowerR.init(m); 


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

    FOR(i, 1, n)
    {
        segLowerL.root[i] = ++segLowerL.curNode;
        segLowerR.root[i] = ++segLowerR.curNode;
        segLowerL.seg[segLowerL.curNode] = segLowerL.seg[segLowerL.root[i - 1]];
        segLowerR.seg[segLowerR.curNode] = segLowerR.seg[segLowerR.root[i - 1]];

        id[i] = lower_bound(ids + 1, ids + n + 1, pll(a[i].second, i)) - ids;

        if (i > 1) segLowerL.upd(segLowerL.root[i], 1, m, id[i - 1], - a[i - 1].first - a[i - 1].second);
        if (i > 1) segLowerR.upd(segLowerR.root[i], 1, m, id[i - 1], - a[i - 1].first + a[i - 1].second);
    }


    FOR(i, 2, n)
    {
        ll cur = get_ans(i);
        if (cur != 1e18) pq.push({cur, i});
    }

    // cerr << segLowerL.get(segLowerL.root[3], 1, m, 1, 1).first << '\n';

    // cerr << "NEXT\n\n";
    // cerr << get_ans(3) << '\n';
    // cerr << get_ans(3) << '\n';


    while (K--)
    {
        pll cur = pq.top(); pq.pop();
        ll nxt = get_ans((int)cur.second);

        cout << cur.first << '\n';
        if (nxt != 1e18) pq.push({nxt, cur.second});
    }
}

signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    #define TASK "TEST"
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        freopen(TASK".OUT", "w", stdout);
    }
    solve();
    return 0;
}

/* NOTES:

*/

Compilation message (stderr)

road_construction.cpp: In function 'int main()':
road_construction.cpp:154:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
road_construction.cpp:155:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |         freopen(TASK".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 27 / 27
• Subtask 6: 35 / 35