제출 #712994

#제출 시각아이디문제언어결과실행 시간메모리
712994MrKusticPalembang Bridges (APIO15_bridge)C++14
100 / 100
209 ms29200 KiB
#include <bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #define all(x) x.begin(), x.end() #define sz(x) (int)x.size() #define pb emplace_back #define x first #define y second #define ff first #define ss second using namespace std; //using namespace __gnu_pbds; typedef long long ll; typedef long double ld; typedef pair<int, int> pt; typedef pair<ll, ll> ptll; typedef complex<double> ftype; //typedef tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; //typedef gp_hash_table<int, int> table; template <typename T1, typename T2> istream& operator>>(istream& is, pair <T1, T2>& a){ is >> a.ff >> a.ss; return is; } template<typename T> istream &operator>>(istream &in, vector<T> &list){ for (auto &x: list) in >> x; return in; } template <typename T1, typename T2> ostream& operator<<(ostream& os, pair <T1, T2> a){ os << a.ff << " " << a.ss << " "; return os; } template<typename T> ostream &operator<<(ostream &out, const vector<T> &list) { for (auto x : list) out << x << " "; return out; } mt19937 rnd(31); void fastio() { ios_base::sync_with_stdio(false); cin.tie(nullptr); } //#pragma GCC optimize(3) /*#pragma GCC target("avx,avx2,sse3,ssse3,sse4.1,sse4.2") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("inline")*/ //------------------------------------------- const int MAXN = 2e5 + 10; pt poses[MAXN]; vector<int> start[MAXN], stop[MAXN]; ll solve1(int n){ if (n == 0) return 0; sort(poses, poses + n, [&](pt a, pt b){return a.y < b.y;}); ll ans = 1e18; vector<int> xs; for (int i = 0; i < n; i++){ xs.push_back(poses[i].x); xs.push_back(poses[i].y); } sort(all(xs)); xs.resize(unique(all(xs)) - xs.begin()); ll sum1 = 0, sum2 = 0, mid = 0; ll cnt1 = 0, cnt2 = 0, cntmid = 0; map<int, int> coords; for (int x: xs) coords[x] = 0; int tt = 0; for (auto &[x, y]: coords) y = tt++; for (int i = 0; i < n; i++){ sum2 += poses[i].x + poses[i].y; cnt2++; start[coords[poses[i].x]].push_back(i); stop[coords[poses[i].y]].push_back(i); } for (int i = 0; i < sz(xs); i++){ ll pos = xs[i]; for (int j: start[i]){ auto [x, y] = poses[j]; sum2 -= x + y; mid += abs(x - y); cnt2--; cntmid++; } for (int j: stop[i]){ auto [x, y] = poses[j]; mid -= abs(x - y); sum1 += x + y; cntmid--; cnt1++; } ans = min(ans, 2 * pos * cnt1 - sum1 + mid + sum2 - 2 * pos * cnt2); } return ans + n; } ll res[MAXN]; ll solve2(int n){ if (n == 0) return 0; if (n == 1) return poses[0].y - poses[0].x + 1; sort(poses, poses + n, [&](pt a, pt b){return a.x + a.y < b.x + b.y;}); multiset<int> l, r; ll sl, sr; sl = sr = 0; ll ans = 1e18; for (int i = 0; i < n; i++){ auto [x1, x2] = poses[i]; for (int x: {x1, x2}) { if (i == 0 || x >= *r.begin()) { r.insert(x); sr += x; } else { l.insert(x); sl += x; } } while (sz(l) < sz(r)){ int x = *r.begin(); r.erase(r.begin()); sr -= x; l.insert(x); sl += x; } while (sz(l) > sz(r) + 1){ int x = *(--l.end()); l.erase(--l.end()); sl -= x; r.insert(x); sr += x; } ll x = *(--l.end()); ll curr = x * sz(l) - sl + sr - x * sz(r); res[i] = curr; } l.clear(); r.clear(); sl = sr = 0; for (int i = n - 1; i > 0; i--){ auto [x1, x2] = poses[i]; for (int x: {x1, x2}) { if (i == 0 || x >= *r.begin()) { r.insert(x); sr += x; } else { l.insert(x); sl += x; } } while (sz(l) < sz(r)){ int x = *r.begin(); r.erase(r.begin()); sr -= x; l.insert(x); sl += x; } while (sz(l) > sz(r) + 1){ int x = *(--l.end()); l.erase(--l.end()); sl -= x; r.insert(x); sr += x; } ll x = *(--l.end()); ll curr = x * sz(l) - sl + sr - x * sz(r); res[i - 1] += curr; } for (int i = 0; i < n - 1; i++) ans = min(ans, res[i]); return ans + n; } void run() { int k, n; k = 2; n = 1e5; cin >> k >> n; ll var = 0; int tt = 0; for (int i = 0; i < n; i++){ char c1, c2; int pos1, pos2; c1 = 'A', c2 = 'B'; pos1 = rnd() % 1000000000, pos2 = rnd() % 1000000000; cin >> c1 >> pos1 >> c2 >> pos2; if (pos1 > pos2) swap(pos1, pos2); if (c1 == c2){ var += abs(pos1 - pos2); } else { poses[tt++] = {pos1, pos2}; } } n = tt; if (k == 1){ cout << var + solve1(n) << '\n'; } else { cout << var + solve2(n) << '\n'; } } int main() { #ifdef LOCAL freopen("input.txt", "r", stdin); #else fastio(); //freopen("", "r", stdin); //freopen("", "w", stdout); #endif auto start = chrono::high_resolution_clock::now(); run(); auto stop = chrono::high_resolution_clock::now(); #ifdef LOCAL cerr << "\nProgram finished in " << (ld)chrono::duration_cast<chrono::milliseconds>(stop - start).count() / 1e3 << " sec\n"; #endif return 0; }

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

bridge.cpp: In function 'll solve1(int)':
bridge.cpp:88:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   88 |     for (auto &[x, y]: coords)
      |                ^
bridge.cpp:99:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   99 |             auto [x, y] = poses[j];
      |                  ^
bridge.cpp:106:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  106 |             auto [x, y] = poses[j];
      |                  ^
bridge.cpp: In function 'll solve2(int)':
bridge.cpp:130:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  130 |         auto [x1, x2] = poses[i];
      |              ^
bridge.cpp:162:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  162 |         auto [x1, x2] = poses[i];
      |              ^
bridge.cpp: In function 'int main()':
bridge.cpp:232:10: warning: variable 'start' set but not used [-Wunused-but-set-variable]
  232 |     auto start = chrono::high_resolution_clock::now();
      |          ^~~~~
bridge.cpp:234:10: warning: variable 'stop' set but not used [-Wunused-but-set-variable]
  234 |     auto stop = chrono::high_resolution_clock::now();
      |          ^~~~
#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...