제출 #1318415

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1318415		wedonttalkanymore	Palembang Bridges (APIO15_bridge)	C++20	22 / 100	106 ms	35964 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 << ' ' << 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);
    }
} 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;
	}
    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';
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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