Submission #1315983

#	Time	Username	Problem	Language	Result	Execution time	Memory
1315983		tkhoi13	Palembang Bridges (APIO15_bridge)	C++20	Compilation error	0 ms	0 KiB

bridge

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define db double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define all(x) begin(x), end(x)
#define allr(x) rbegin(x), rend(x)
#define szx(x) ((int)(x).size())
#define FOR(i, a, b) for (int i = a, _b = (b); i <= _b; ++i)
#define ROF(i, a, b) for (int i = a, _b = (b); i >= _b; --i)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define endl '\n'
#define inf 1000000007
#define mod 1000000007
// #define mod 998244353

using namespace std;
using namespace __gnu_pbds;

void setIO() {
    ios::sync_with_stdio(0);
    cin.tie(0);
}
void openFile(string filename = "") {
    if (!filename.empty())
        if (ifstream(filename + ".in")) {
            freopen((filename + ".in").c_str(), "r", stdin);
            freopen((filename + ".out").c_str(), "w", stdout);
        }
}

const int MAX = 1e5 + 5;
int n, k;
vector<pll> a;
vector<int> compress{-1};
ll s1 = 0;

struct SegmentTree {
    vector<pair<int, ll>> st;
    int _n;
    SegmentTree(int _n) {
        n = _n;
        st.resize(4 * n);
    }

    void update(pii x, int s = 1) {
        update(x.fi, s, s * compress[x.fi]);
        update(x.se, s, s * compress[x.se]);
    }

    void update(int x, int y, ll z, int id = 1, int l = 1, int r = n) {
        if (l == r) {
            st[id].fi += y;
            st[id].se += z;
            return;
        }
        int mid = (l + r) >> 1;
        if (x <= mid)
            update(x, y, z, 2 * id, l, mid);
        else
            update(x, y, z, 2 * id + 1, mid + 1, r);
        st[id].fi = st[2 * id].fi + st[2 * id + 1].fi;
        st[id].se = st[2 * id].se + st[2 * id + 1].se;
    }

    int med(int id = 1, int l = 1, int r = n, int acc = 0) {
        if (l == r) return l;
        int mid = (l + r) >> 1;
        if (acc + st[2 * id].fi > getmid())
            return med(2 * id, l, mid, acc);
        else
            return med(2 * id + 1, mid + 1, r, acc + st[2 * id].fi);
    }

    pair<int, ll> query(int u, int v = n, int id = 1, int l = 1, int r = n) {
        if (u > v) return {0, 0};
        if (r < u || l > v) return {0, 0};
        if (l >= u && r <= v) return st[id];
        int mid = (l + r) >> 1;

        pair<int, ll> q1 = query(u, v, 2 * id, l, mid);
        pair<int, ll> q2 = query(u, v, 2 * id + 1, mid + 1, r);

        return {q1.fi + q2.fi, q1.se + q2.se};
    }

    int getmid() { return (st[1].fi + 1) / 2; }

    ll getans() {
        int m = med();
        pair<int, ll> q1 = query(1, m - 1), q2 = query(m + 1);
        return q2.se - q1.se - 1LL * (q2.fi - q1.fi) * compress[m];
    }
};

void solve() {
    int m = szx(a);
    s1 += m;
    REP(i, m) compress.pb(a[i].fi), compress.pb(a[i].se);
    sort(all(compress));
    sort(all(a), [&](pll x, pll y) { return x.fi + x.se < y.fi + y.se; });
    compress.erase(unique(all(compress)), compress.end());

    SegmentTree pref(szx(compress)), suff(szx(compress));
    REP(i, m) {
        a[i].fi = lower_bound(all(compress), a[i].fi) - compress.begin();
        a[i].se = lower_bound(all(compress), a[i].se) - compress.begin();
        suff.update(a[i]);
    }

    ll ans = m != 0 ? 1e18 : 0;

    if (k == 1)
        ans = suff.getans();
    else
        REP(i, m) {
            ans = min(ans, pref.getans() + suff.getans());
            suff.update(a[i], -1);
            pref.update(a[i]);
        }

    cout << s1 + ans;
}

void input() {
    cin >> k >> n;
    REP(i, n) {
        char A, B;
        int s, t;
        cin >> A >> s >> B >> t;

        if (A != B)
            a.pb({s, t});
        else
            s1 += abs(s - t);
    }
}

void preprocess() {}

void reset() {}

int main() {
    setIO();
    openFile("main");
    int t = 1;
    // cin >> t;
    preprocess();
    while (t--) {
        reset();
        input();
        solve();
    }
}#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define db double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define all(x) begin(x), end(x)
#define allr(x) rbegin(x), rend(x)
#define szx(x) ((int)(x).size())
#define FOR(i, a, b) for (int i = a, _b = (b); i <= _b; ++i)
#define ROF(i, a, b) for (int i = a, _b = (b); i >= _b; --i)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define endl '\n'
#define inf 1000000007
#define mod 1000000007
// #define mod 998244353

using namespace std;
using namespace __gnu_pbds;

void setIO() {
    ios::sync_with_stdio(0);
    cin.tie(0);
}
void openFile(string filename = "") {
    if (!filename.empty())
        if (ifstream(filename + ".in")) {
            freopen((filename + ".in").c_str(), "r", stdin);
            freopen((filename + ".out").c_str(), "w", stdout);
        }
}

const int MAX = 1e5 + 5;
int n, k;
vector<pll> a;
vector<int> compress{-1};
ll s1 = 0;

struct SegmentTree {
    vector<pair<int, ll>> st;
    int _n;
    SegmentTree(int _n) {
        n = _n;
        st.resize(4 * n);
    }

    void update(pii x, int s = 1) {
        update(x.fi, s, s * compress[x.fi]);
        update(x.se, s, s * compress[x.se]);
    }

    void update(int x, int y, ll z, int id = 1, int l = 1, int r = n) {
        if (l == r) {
            st[id].fi += y;
            st[id].se += z;
            return;
        }
        int mid = (l + r) >> 1;
        if (x <= mid)
            update(x, y, z, 2 * id, l, mid);
        else
            update(x, y, z, 2 * id + 1, mid + 1, r);
        st[id].fi = st[2 * id].fi + st[2 * id + 1].fi;
        st[id].se = st[2 * id].se + st[2 * id + 1].se;
    }

    int med(int id = 1, int l = 1, int r = n, int acc = 0) {
        if (l == r) return l;
        int mid = (l + r) >> 1;
        if (acc + st[2 * id].fi > getmid())
            return med(2 * id, l, mid, acc);
        else
            return med(2 * id + 1, mid + 1, r, acc + st[2 * id].fi);
    }

    pair<int, ll> query(int u, int v = n, int id = 1, int l = 1, int r = n) {
        if (u > v) return {0, 0};
        if (r < u || l > v) return {0, 0};
        if (l >= u && r <= v) return st[id];
        int mid = (l + r) >> 1;

        pair<int, ll> q1 = query(u, v, 2 * id, l, mid);
        pair<int, ll> q2 = query(u, v, 2 * id + 1, mid + 1, r);

        return {q1.fi + q2.fi, q1.se + q2.se};
    }

    int getmid() { return (st[1].fi + 1) / 2; }

    ll getans() {
        int m = med();
        pair<int, ll> q1 = query(1, m - 1), q2 = query(m + 1);
        return q2.se - q1.se - 1LL * (q2.fi - q1.fi) * compress[m];
    }
};

void solve() {
    int m = szx(a);
    s1 += m;
    REP(i, m) compress.pb(a[i].fi), compress.pb(a[i].se);
    sort(all(compress));
    sort(all(a), [&](pll x, pll y) { return x.fi + x.se < y.fi + y.se; });
    compress.erase(unique(all(compress)), compress.end());

    SegmentTree pref(szx(compress)), suff(szx(compress));
    REP(i, m) {
        a[i].fi = lower_bound(all(compress), a[i].fi) - compress.begin();
        a[i].se = lower_bound(all(compress), a[i].se) - compress.begin();
        suff.update(a[i]);
    }

    ll ans = m != 0 ? 1e18 : 0;

    if (k == 1)
        ans = suff.getans();
    else
        REP(i, m) {
            ans = min(ans, pref.getans() + suff.getans());
            suff.update(a[i], -1);
            pref.update(a[i]);
        }

    cout << s1 + ans;
}

void input() {
    cin >> k >> n;
    REP(i, n) {
        char A, B;
        int s, t;
        cin >> A >> s >> B >> t;

        if (A != B)
            a.pb({s, t});
        else
            s1 += abs(s - t);
    }
}

void preprocess() {}

void reset() {}

int main() {
    setIO();
    openFile("main");
    int t = 1;
    // cin >> t;
    preprocess();
    while (t--) {
        reset();
        input();
        solve();
    }
}

Compilation message (stderr)

bridge.cpp:159:2: error: stray '#' in program
  159 | }#include <bits/stdc++.h>
      |  ^
bridge.cpp:159:12: error: 'bits' was not declared in this scope
  159 | }#include <bits/stdc++.h>
      |            ^~~~
bridge.cpp:159:17: error: 'stdc' was not declared in this scope; did you mean 'std'?
  159 | }#include <bits/stdc++.h>
      |                 ^~~~
      |                 std
bridge.cpp:159:12: error: 'bits' was not declared in this scope
  159 | }#include <bits/stdc++.h>
      |            ^~~~
bridge.cpp:159:17: error: 'stdc' was not declared in this scope; did you mean 'std'?
  159 | }#include <bits/stdc++.h>
      |                 ^~~~
      |                 std
bridge.cpp:159:12: error: 'bits' was not declared in this scope
  159 | }#include <bits/stdc++.h>
      |            ^~~~
bridge.cpp:159:17: error: 'stdc' was not declared in this scope; did you mean 'std'?
  159 | }#include <bits/stdc++.h>
      |                 ^~~~
      |                 std
bridge.cpp:159:12: error: 'bits' was not declared in this scope
  159 | }#include <bits/stdc++.h>
      |            ^~~~
bridge.cpp:159:17: error: 'stdc' was not declared in this scope; did you mean 'std'?
  159 | }#include <bits/stdc++.h>
      |                 ^~~~
      |                 std
bridge.cpp:159:12: error: 'bits' was not declared in this scope
  159 | }#include <bits/stdc++.h>
      |            ^~~~
bridge.cpp:159:17: error: 'stdc' was not declared in this scope; did you mean 'std'?
  159 | }#include <bits/stdc++.h>
      |                 ^~~~
      |                 std
bridge.cpp:159:12: error: 'bits' was not declared in this scope
  159 | }#include <bits/stdc++.h>
      |            ^~~~
bridge.cpp:159:17: error: 'stdc' was not declared in this scope; did you mean 'std'?
  159 | }#include <bits/stdc++.h>
      |                 ^~~~
      |                 std
bridge.cpp:159:12: error: 'bits' was not declared in this scope
  159 | }#include <bits/stdc++.h>
      |            ^~~~
bridge.cpp:159:17: error: 'stdc' was not declared in this scope; did you mean 'std'?
  159 | }#include <bits/stdc++.h>
      |                 ^~~~
      |                 std
bridge.cpp:159:12: error: 'bits' was not declared in this scope
  159 | }#include <bits/stdc++.h>
      |            ^~~~
bridge.cpp:159:17: error: 'stdc' was not declared in this scope; did you mean 'std'?
  159 | }#include <bits/stdc++.h>
      |                 ^~~~
      |                 std
bridge.cpp:159:12: error: 'bits' was not declared in this scope
  159 | }#include <bits/stdc++.h>
      |            ^~~~
bridge.cpp:159:17: error: 'stdc' was not declared in this scope; did you mean 'std'?
  159 | }#include <bits/stdc++.h>
      |                 ^~~~
      |                 std
bridge.cpp:159:3: error: 'include' does not name a type
  159 | }#include <bits/stdc++.h>
      |   ^~~~~~~
bridge.cpp:183:6: error: redefinition of 'void setIO()'
  183 | void setIO() {
      |      ^~~~~
bridge.cpp:25:6: note: 'void setIO()' previously defined here
   25 | void setIO() {
      |      ^~~~~
bridge.cpp:187:6: error: redefinition of 'void openFile(std::string)'
  187 | void openFile(string filename = "") {
      |      ^~~~~~~~
bridge.cpp:29:6: note: 'void openFile(std::string)' previously defined here
   29 | void openFile(string filename = "") {
      |      ^~~~~~~~
bridge.cpp:195:11: error: redefinition of 'const int MAX'
  195 | const int MAX = 1e5 + 5;
      |           ^~~
bridge.cpp:37:11: note: 'const int MAX' previously defined here
   37 | const int MAX = 1e5 + 5;
      |           ^~~
bridge.cpp:196:5: error: redefinition of 'int n'
  196 | int n, k;
      |     ^
bridge.cpp:38:5: note: 'int n' previously declared here
   38 | int n, k;
      |     ^
bridge.cpp:196:8: error: redefinition of 'int k'
  196 | int n, k;
      |        ^
bridge.cpp:38:8: note: 'int k' previously declared here
   38 | int n, k;
      |        ^
bridge.cpp:197:13: error: redefinition of 'std::vector<std::pair<long long int, long long int> > a'
  197 | vector<pll> a;
      |             ^
bridge.cpp:39:13: note: 'std::vector<std::pair<long long int, long long int> > a' previously defined here
   39 | vector<pll> a;
      |             ^
bridge.cpp:198:13: error: redefinition of 'std::vector<int> compress'
  198 | vector<int> compress{-1};
      |             ^~~~~~~~
bridge.cpp:40:13: note: 'std::vector<int> compress' previously declared here
   40 | vector<int> compress{-1};
      |             ^~~~~~~~
bridge.cpp:199:4: error: redefinition of 'long long int s1'
  199 | ll s1 = 0;
      |    ^~
bridge.cpp:41:4: note: 'long long int s1' previously defined here
   41 | ll s1 = 0;
      |    ^~
bridge.cpp:201:8: error: redefinition of 'struct SegmentTree'
  201 | struct SegmentTree {
      |        ^~~~~~~~~~~
bridge.cpp:43:8: note: previous definition of 'struct SegmentTree'
   43 | struct SegmentTree {
      |        ^~~~~~~~~~~
bridge.cpp:259:6: error: redefinition of 'void solve()'
  259 | void solve() {
      |      ^~~~~
bridge.cpp:101:6: note: 'void solve()' previously defined here
  101 | void solve() {
      |      ^~~~~
bridge.cpp:288:6: error: redefinition of 'void input()'
  288 | void input() {
      |      ^~~~~
bridge.cpp:130:6: note: 'void input()' previously defined here
  130 | void input() {
      |      ^~~~~
bridge.cpp:302:6: error: redefinition of 'void preprocess()'
  302 | void preprocess() {}
      |      ^~~~~~~~~~
bridge.cpp:144:6: note: 'void preprocess()' previously defined here
  144 | void preprocess() {}
      |      ^~~~~~~~~~
bridge.cpp:304:6: error: redefinition of 'void reset()'
  304 | void reset() {}
      |      ^~~~~
bridge.cpp:146:6: note: 'void reset()' previously defined here
  146 | void reset() {}
      |      ^~~~~
bridge.cpp:306:5: error: redefinition of 'int main()'
  306 | int main() {
      |     ^~~~
bridge.cpp:148:5: note: 'int main()' previously defined here
  148 | int main() {
      |     ^~~~
bridge.cpp: In function 'void openFile(std::string)':
bridge.cpp:32:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |             freopen((filename + ".in").c_str(), "r", stdin);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:33:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |             freopen((filename + ".out").c_str(), "w", stdout);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp: In function 'void openFile(std::string)':
bridge.cpp:190:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  190 |             freopen((filename + ".in").c_str(), "r", stdin);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:191:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  191 |             freopen((filename + ".out").c_str(), "w", stdout);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~