Submission #642116

#TimeUsernameProblemLanguageResultExecution timeMemory
642116ghostwriterPalembang Bridges (APIO15_bridge)C++14
100 / 100
398 ms7728 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include <debug.h> #endif #define st first #define nd second #define pb push_back #define pf push_front #define _pb pop_back #define _pf pop_front #define lb lower_bound #define ub upper_bound #define mtp make_tuple #define all(x) (x).begin(), (x).end() #define sz(x) (int)(x).size() typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ldb; typedef pair<int, int> pi; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll; typedef string str; template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); } template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; } #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i)) #define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i)) #define EACH(i, x) for (auto &(i) : (x)) #define WHILE while #define file "TEST" mt19937 rd(chrono::steady_clock::now().time_since_epoch().count()); ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); } /* Tran The Bao CTL - Da Lat Cay ngay cay dem nhung deo duoc cong nhan */ const ll oo = 2e18; int k, n; vpi a; ll tv = 0, rs = oo; namespace subtask1 { void solve() { vi b; FOR(i, 1, n) { b.pb(a[i].st); b.pb(a[i].nd); } EACH(i, b) { ll sum = 0; FOR(j, 1, n) if (a[j].nd <= i) sum += 2 * i - a[j].st - a[j].nd + 1; else if (a[j].st >= i) sum += a[j].st + a[j].nd - 2 * i + 1; else sum += a[j].nd - a[j].st + 1; rs = min(rs, sum); } cout << tv + rs; } } namespace subtask2 { const int N = 2e5 + 5; int prec[N], sufc[N]; ll pres[N], sufs[N]; bool cmp(pi &a, pi &b) { return a.nd < b.nd; } bool cmp1(pi &a, pi &b) { return a.st > b.st; } void solve() { FOR(i, 1, n) tv += a[i].nd - a[i].st + 1; vi b; FOR(i, 1, n) { b.pb(a[i].st); b.pb(a[i].nd); } sort(a.begin() + 1, a.end(), cmp); sort(all(b)); int l = 1, cnt = 0; ll sum = 0; FOR(i, 0, sz(b) - 1) { int x = b[i]; WHILE(l <= n && a[l].nd < x) { ++cnt; sum += 2 * a[l].nd; ++l; } prec[i] = cnt; pres[i] = sum; } sort(a.begin() + 1, a.end(), cmp1); l = 1; cnt = 0; sum = 0; FOS(i, sz(b) - 1, 0) { int x = b[i]; WHILE(l <= n && a[l].st > x) { ++cnt; sum += 2 * a[l].st; ++l; } sufc[i] = cnt; sufs[i] = sum; } FOR(i, 0, sz(b) - 1) { int x = b[i]; rs = min(rs, 2LL * x * prec[i] - pres[i] + sufs[i] - 2LL * x * sufc[i]); } cout << tv + rs; } } namespace subtask3 { void solve() { vi b; FOR(i, 1, n) { b.pb(a[i].st); b.pb(a[i].nd); } sort(all(b)); FOR(i, 0, sz(b) - 1) FOR(j, i, sz(b) - 1) { int x = b[i], y = b[j]; ll sum = 0; FOR(z, 1, n) if (a[z].nd < x) sum += 2 * x - a[z].st - a[z].nd + 1; else if (a[z].st > y) sum += a[z].st + a[z].nd - 2 * y + 1; else if (x < a[z].st && a[z].nd < y) sum += min(a[z].st + a[z].nd - 2 * x + 1, 2 * y - a[z].st - a[z].nd + 1); else sum += a[z].nd - a[z].st + 1; rs = min(rs, sum); } cout << tv + rs; } } namespace subtask4 { #define int long long const int N = 2005; pll f[N]; vi b; void upd(int ps, pi v) { ++ps; for (int i = ps; i < N; i += (i & -i)) { f[i].st += v.st; f[i].nd += v.nd; } } void upd(int l, int r, pi v) { upd(l, {v.nd, v.st - b[l] * v.nd}); upd(r + 1, {-v.nd, -v.st + b[l] * v.nd}); } pll get(int ps) { ++ps; pll rs = {0, 0}; for (int i = ps; i > 0; i -= (i & -i)) { rs.st += f[i].st; rs.nd += f[i].nd; } return rs; } ll getv(int ps) { pll cur = get(ps); return cur.st * b[ps] + cur.nd; } void updr(int l, int r, pi v) { if (l > r || l > b.back()) return; int ps1 = lb(all(b), l) - b.begin(), ps2; if (b.back() <= r) ps2 = sz(b) - 1; else ps2 = ub(all(b), r) - b.begin() - 1; if (ps1 > ps2) return; upd(ps1, ps2, {v.st + (b[ps1] - l) * v.nd, v.nd}); } void solve() { FOR(i, 1, n) { b.pb(a[i].st); b.pb(a[i].nd); } sort(all(b)); FOR(i, 0, sz(b) - 1) { FOR(j, 0, N - 1) f[j] = {0, 0}; int x = b[i]; ll sum = 0; FOR(j, 1, n) if (a[j].nd < x) sum += 2 * x - a[j].st - a[j].nd + 1; else if (a[j].st <= x) sum += a[j].nd - a[j].st + 1; else { updr(x, a[j].st - 1, {a[j].st + a[j].nd - 2 * x + 1, -2}); updr(a[j].st, a[j].nd, {a[j].nd - a[j].st + 1, 0}); updr(a[j].nd + 1, a[j].nd + a[j].st - x, {2 + a[j].nd - a[j].st + 1, 2}); updr(a[j].nd + a[j].st - x + 1, b.back(), {a[j].st + a[j].nd - 2 * x + 1, 0}); } FOR(j, i, sz(b) - 1) rs = min(rs, sum + getv(j)); } cout << tv + rs; } } namespace subtask5 { const int N = 1e5 + 5; const int Nx2 = 2e5 + 5; ll pre[N], suf[N]; pll f[Nx2]; vpi b; vi v; int getpos(int x) { return lb(all(v), x) - v.begin(); } void upd(int pos, pll v) { for (int i = pos; i < Nx2; i += (i & -i)) { f[i].st += v.st; f[i].nd += v.nd; } } pll get(int pos) { pll rs = {0, 0}; for (int i = pos; i > 0; i -= (i & -i)) { rs.st += f[i].st; rs.nd += f[i].nd; } return rs; } int getmed() { pll tmp = get(Nx2 - 1); int num = tmp.st, cur = 0, cnt = 0, rs = Nx2; FOS(i, 17, 0) { if ((cur | (1 << i)) >= Nx2) continue; if (cnt + f[cur | (1 << i)].st >= (num + 1) / 2) rs = min(rs, cur | (1 << i)); else { cur |= 1 << i; cnt += f[cur].st; } } return rs; } void solve() { tv += n; b.resize(n + 1, {-1, -1}); FOR(i, 1, n) b[i] = {a[i].st + a[i].nd, i}; sort(all(b)); v.pb(-1); FOR(i, 1, n) { v.pb(a[i].st); v.pb(a[i].nd); } sort(all(v)); FOR(i, 1, n) { int pos1 = getpos(a[b[i].nd].st), pos2 = getpos(a[b[i].nd].nd); upd(pos1, {1, a[b[i].nd].st}); upd(pos2, {1, a[b[i].nd].nd}); int med = getmed(); pll cur = get(Nx2 - 1); int cnt = cur.st; ll sum = cur.nd; pll tmp = get(med); int cnt1 = tmp.st; ll sum1 = tmp.nd; cnt -= cnt1; sum -= sum1; pre[i] = sum - 1LL * cnt * v[med] + 1LL * cnt1 * v[med] - sum1; } FOR(i, 0, Nx2 - 1) f[i] = {0, 0}; FOS(i, n, 1) { int pos1 = getpos(a[b[i].nd].st), pos2 = getpos(a[b[i].nd].nd); upd(pos1, {1, a[b[i].nd].st}); upd(pos2, {1, a[b[i].nd].nd}); int med = getmed(); pll cur = get(Nx2 - 1); int cnt = cur.st; ll sum = cur.nd; pll tmp = get(med); int cnt1 = tmp.st; ll sum1 = tmp.nd; cnt -= cnt1; sum -= sum1; suf[i] = sum - 1LL * cnt * v[med] + 1LL * cnt1 * v[med] - sum1; } FOR(i, 0, n) rs = min(rs, pre[i] + suf[i + 1]); cout << tv + rs; } } signed main() { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); // freopen(file".inp", "r", stdin); // freopen(file".out", "w", stdout); cin >> k >> n; a.pb({0, 0}); FOR(i, 1, n) { char p, q; int s, t; cin >> p >> s >> q >> t; if (p == q) tv += abs(s - t); else a.pb({min(s, t), max(s, t)}); } n = sz(a) - 1; if (n == 0) { cout << tv; return 0; } if (k == 1 && n <= 1e3) { subtask1::solve(); return 0; } if (k == 1 && n <= 1e5) { subtask2::solve(); return 0; } if (k == 2 && n <= 1e2) { subtask3::solve(); return 0; } if (k == 2 && n <= 1e3) { subtask4::solve(); return 0; } subtask5::solve(); return 0; } /* 2 5 B 0 A 4 B 1 B 3 A 5 B 7 B 2 A 6 B 1 A 7 */

Compilation message (stderr)

bridge.cpp: In function 'void subtask1::solve()':
bridge.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
bridge.cpp:43:3: note: in expansion of macro 'FOR'
   43 |   FOR(i, 1, n) {
      |   ^~~
bridge.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
bridge.cpp:47:3: note: in expansion of macro 'EACH'
   47 |   EACH(i, b) {
      |   ^~~~
bridge.cpp:24:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
bridge.cpp:49:4: note: in expansion of macro 'FOR'
   49 |    FOR(j, 1, n)
      |    ^~~
bridge.cpp: In function 'void subtask2::solve()':
bridge.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
bridge.cpp:65:3: note: in expansion of macro 'FOR'
   65 |   FOR(i, 1, n) tv += a[i].nd - a[i].st + 1;
      |   ^~~
bridge.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
bridge.cpp:67:3: note: in expansion of macro 'FOR'
   67 |   FOR(i, 1, n) {
      |   ^~~
bridge.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
bridge.cpp:75:3: note: in expansion of macro 'FOR'
   75 |   FOR(i, 0, sz(b) - 1) {
      |   ^~~
bridge.cpp:25:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   25 | #define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
      |                               ^
bridge.cpp:89:3: note: in expansion of macro 'FOS'
   89 |   FOS(i, sz(b) - 1, 0) {
      |   ^~~
bridge.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
bridge.cpp:99:3: note: in expansion of macro 'FOR'
   99 |   FOR(i, 0, sz(b) - 1) {
      |   ^~~
bridge.cpp: In function 'void subtask3::solve()':
bridge.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
bridge.cpp:109:3: note: in expansion of macro 'FOR'
  109 |   FOR(i, 1, n) {
      |   ^~~
bridge.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
bridge.cpp:114:3: note: in expansion of macro 'FOR'
  114 |   FOR(i, 0, sz(b) - 1)
      |   ^~~
bridge.cpp:24:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
bridge.cpp:115:3: note: in expansion of macro 'FOR'
  115 |   FOR(j, i, sz(b) - 1) {
      |   ^~~
bridge.cpp:24:31: warning: unnecessary parentheses in declaration of 'z' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
bridge.cpp:118:4: note: in expansion of macro 'FOR'
  118 |    FOR(z, 1, n)
      |    ^~~
bridge.cpp: In function 'void subtask4::solve()':
bridge.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
bridge.cpp:166:3: note: in expansion of macro 'FOR'
  166 |   FOR(i, 1, n) {
      |   ^~~
bridge.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
bridge.cpp:171:3: note: in expansion of macro 'FOR'
  171 |   FOR(i, 0, sz(b) - 1) {
      |   ^~~
bridge.cpp:24:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
bridge.cpp:172:4: note: in expansion of macro 'FOR'
  172 |    FOR(j, 0, N - 1) f[j] = {0, 0};
      |    ^~~
bridge.cpp:24:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
bridge.cpp:175:4: note: in expansion of macro 'FOR'
  175 |    FOR(j, 1, n)
      |    ^~~
bridge.cpp:24:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
bridge.cpp:184:4: note: in expansion of macro 'FOR'
  184 |    FOR(j, i, sz(b) - 1) rs = min(rs, sum + getv(j));
      |    ^~~
bridge.cpp: In function 'long long int subtask5::getmed()':
bridge.cpp:25:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   25 | #define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
      |                               ^
bridge.cpp:214:3: note: in expansion of macro 'FOS'
  214 |   FOS(i, 17, 0) {
      |   ^~~
bridge.cpp: In function 'void subtask5::solve()':
bridge.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
bridge.cpp:227:3: note: in expansion of macro 'FOR'
  227 |   FOR(i, 1, n) b[i] = {a[i].st + a[i].nd, i};
      |   ^~~
bridge.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
bridge.cpp:230:3: note: in expansion of macro 'FOR'
  230 |   FOR(i, 1, n) {
      |   ^~~
bridge.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
bridge.cpp:235:3: note: in expansion of macro 'FOR'
  235 |   FOR(i, 1, n) {
      |   ^~~
bridge.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
bridge.cpp:245:3: note: in expansion of macro 'FOR'
  245 |   FOR(i, 0, Nx2 - 1) f[i] = {0, 0};
      |   ^~~
bridge.cpp:25:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   25 | #define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
      |                               ^
bridge.cpp:246:3: note: in expansion of macro 'FOS'
  246 |   FOS(i, n, 1) {
      |   ^~~
bridge.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
bridge.cpp:256:3: note: in expansion of macro 'FOR'
  256 |   FOR(i, 0, n) rs = min(rs, pre[i] + suf[i + 1]);
      |   ^~~
bridge.cpp: In function 'int main()':
bridge.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
bridge.cpp:266:5: note: in expansion of macro 'FOR'
  266 |     FOR(i, 1, n) {
      |     ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...