Submission #1318475

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318475		wedonttalkanymore	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	232 ms	23196 KiB

bridge

#include <bits/stdc++.h>
/*
    Chang ki si xuyen man dem
    Di lac vao trong giac mong
*/
using namespace std;
using ll = long long;

#define int long long
#define pii pair<ll, ll>
#define fi first
#define se second

const ll N = 1e5 + 5, inf = 1e18, mod = 1e9 + 7, block = 320, lim = 19;

int k, n;

struct item {
    char p, q;
    int s, t;
};
item a[N], b[N];
int sz, S;
vector <int> comp;

bool cmp(item x, item y) {
    return x.s + x.t < y.s + y.t;
}

struct ST {
    pii st[8 * N]; // fi la so luong, se la tong
//    int tree[8 * N];
    void update(int i, int l, int r, int pos, int val, int tt) {
        if (l == r) {
            st[i].fi += val;
            st[i].se += val * comp[pos - 1];
//            tree[i] += tt;
            return;
        }
        int mid = (l + r) / 2;
        if (pos <= mid) update(2 * i, l, mid, pos, val, tt);
        else update(2 * i + 1, mid + 1, r, pos, val, tt);
        st[i].fi = st[2 * i].fi + st[2 * i + 1].fi;
        st[i].se = st[2 * i].se + st[2 * i + 1].se;
//        tree[i] = tree[2 * i] + tree[2 * i + 1];
    }
    int get_med(int i, int l, int r, int val) {
    	if (l > r) return 0;
        if (l == r) return l;
        if (st[i].fi < val) return 0;
        int mid = (l + r) / 2;
        int ans = 0;
//        cout << i << ' ' << l << ' ' << r << ' ' << val << ' ' << mid << ' ' << st[2 * i].fi << ' ' << st[2 * i + 1].fi << '\n';
        if (st[2 * i].fi >= val) ans = get_med(2 * i, l, mid, val);
        if (!ans) ans = get_med(2 * i + 1, mid + 1, r, val - st[2 * i].fi);
        return ans;
    }
    pii get1(int i, int l, int r, int u, int v) {
        if (u > r || v < l) return make_pair(0, 0);
        if (u <= l && r <= v) return st[i];
        int mid = (l + r) / 2;
        pii valL = get1(2 * i, l, mid, u, v);
        pii valR = get1(2 * i + 1, mid + 1, r, u, v);
        return make_pair(valL.fi + valR.fi, valL.se + valR.se);
    }
//    int get2(int i, int l, int r, int u, int v) {
//    	if (u > r || v < l) return 0;
//        if (u <= l && r <= v) return tree[i];
//        int mid = (l + r) / 2;
//        return get2(2 * i, l, mid, u, v) + get2(2 * i + 1, mid + 1, r, u, v);
//	}
} st1, st2;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    if (fopen(".inp", "r")) {
        freopen(".inp", "r", stdin);
        freopen(".out", "w", stdout);
    }
    cin >> k >> n;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].p >> a[i].s >> a[i].q >> a[i].t;
        if (a[i].p != a[i].q) {
            comp.push_back(a[i].s);
            comp.push_back(a[i].t);
            b[++sz] = a[i];
        }
        else {
        	ans += abs(a[i].t - a[i].s);
		}
    }
    if (sz == 0) {
	    cout << ans << '\n';
	    return 0;
	}
//	for (int i = 1; i <= sz; i++) {
//		cout << b[i].s << ' ' << b[i].t << '\n';
//	}
    sort(b + 1, b + sz + 1, cmp);
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
//    for (auto x : comp) cout << x << ' ';
//    cout << '\n';
    S = comp.size();
//    cout << "size: " << S << '\n';
    for (int i = 1; i <= sz; i++) {
        b[i].s = lower_bound(comp.begin(), comp.end(), b[i].s) - comp.begin() + 1;
        b[i].t = lower_bound(comp.begin(), comp.end(), b[i].t) - comp.begin() + 1;
    }
    for (int i = 1; i <= sz; i++) {
        st2.update(1, 1, S, b[i].s, 1, 1);
        st2.update(1, 1, S, b[i].t, 1, 0);
    }
    if (k == 1) {
        auto p = st2.get_med(1, 1, S, sz);
//        cout << p << ' ' << comp[p - 1] << '\n';
        pii valL = st2.get1(1, 1, S, 1, p);
        pii valR = st2.get1(1, 1, S, p + 1, S);
//        cout << valL.se << ' ' << valR.se << '\n';
        ans += comp[p - 1] * valL.fi - valL.se;
        ans += valR.se - comp[p - 1] * valR.fi;
        ans += sz;
        cout << ans << '\n';
    }
    else {
    	int res = inf;
    	for (int i = 1; i < sz; i++) {
//    		cout << "value: " << b[i].s << ' ' << b[i].t << '\n';
    		int tmp = ans;
    		st1.update(1, 1, S, b[i].s, 1, 1);
    		st1.update(1, 1, S, b[i].t, 1, 0);
    		st2.update(1, 1, S, b[i].s, -1, -1);
    		st2.update(1, 1, S, b[i].t, -1, 0);
    		{
//    			if (i == 3) {
//    				cout << "now: " << '\n';
//				}
    			auto p = st1.get_med(1, 1, S, i);
//    			if (i == 3) {
//    				cout << "at: " << '\n';
//    				cout << p << ' ' << comp[p - 1] << '\n';
//				}
    			pii valL = st1.get1(1, 1, S, 1, p);
    			pii valR = st1.get1(1, 1, S, p + 1, S);
    			tmp += comp[p - 1] * valL.fi - valL.se;
    			tmp += valR.se - comp[p - 1] * valR.fi;
//    			int add = st1.get2(1, 1, S, 1, S);
				int add = i;
    			tmp += add;
			}
			{
				auto p = st2.get_med(1, 1, S, (sz - i));
				pii valL = st2.get1(1, 1, S, 1, p);
				pii valR = st2.get1(1, 1, S, p + 1, S);
				tmp += comp[p - 1] * valL.fi - valL.se;
    			tmp += valR.se - comp[p - 1] * valR.fi;
//    			int add = st2.get2(1, 1, S, 1, S);
				int add = (sz - i); 
    			tmp += add;
			}
//			cout << i << ' ' << tmp << '\n';
			res = min(res, tmp);
		}
		cout << res << '\n';
	}
    return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         freopen(".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
bridge.cpp:79:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         freopen(".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 37 / 37