제출 #635542

#제출 시각아이디문제언어결과실행 시간메모리
635542Do_you_copyPalembang Bridges (APIO15_bridge)C++17
22 / 100
80 ms81880 KiB
#include <bits/stdc++.h> //#define int long long #define fi first #define se second #define pb push_back #define faster ios_base::sync_with_stdio(0); cin.tie(0); using namespace std; using ll = long long; using ull = unsigned ll; using ld = long double; using pii = pair <int, int>; using pil = pair <int, ll>; using pli = pair <ll, int>; using pll = pair <ll, ll>; mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count()); ll min(const ll &a, const ll &b){ return (a < b) ? a : b; } ll max(const ll &a, const ll &b){ return (a > b) ? a : b; } //const ll Mod = 1000000007; //const ll Mod2 = 999999999989; //only use when required const int maxN = 3e5 + 1; const ll inf = 0x3f3f3f3f3f3f3f3f; int n, k; vector <int> val[maxN * 4]; vector <ll> sum[maxN * 4]; vector <int> b; ll pre[maxN], suf[maxN]; int wt_sz = 1; struct TNode{ int l, r; int lp, rp; TNode(){ l = r = lp = rp = 0; } TNode(int _l, int _r) : l(_l), r(_r){}; }; TNode wt[maxN * 4]; void build(int id, auto i, auto j, int l, int r){ wt[id].l = l; wt[id].r = r; if (l == r){ return; } val[id].pb(0); sum[id].pb(0); int mid = (l + r) / 2; int maxx = l, minn = r; for (auto it = i; it != j; ++it){ bool t = *it <= mid; val[id].pb(val[id].back() + t); sum[id].pb(sum[id].back() + *it * t); if (t) maxx = max(maxx, *it); else minn = min(minn, *it); } auto p = stable_partition(i, j,[=](const auto &w){ return w <= mid; }); wt[id].lp = ++wt_sz; wt[id].rp = ++wt_sz; build(wt[id].lp, i, p, l, maxx); build(wt[id].rp, p, j, minn, r); } ll get(int k, int i, int j){ if (k == 0) return 0; --i; ll res = 0; int id = 1; int l = wt[id].l, r = wt[id].r; while (l < r){ int mid = (l + r) / 2; if (k <= val[id][j] - val[id][i]){ i = val[id][i]; j = val[id][j]; id = wt[id].lp; } else{ res += sum[id][j] - sum[id][i]; k -= val[id][j] - val[id][i]; i -= val[id][i]; j -= val[id][j]; id = wt[id].rp; } l = wt[id].l, r = wt[id].r; } res += k * l; return res; } void Init(){ cin >> k >> n; if (k == 1){ ll ans = 0; vector <ll> v; for (ll i = 1; i <= n; ++i){ char p, q; ll s, t; cin >> p >> s >> q >> t; if (p != q){ ++ans; v.pb(s); v.pb(t); } else{ ans += abs(s - t); } } v.push_back(0); sort(v.begin(), v.end()); ll m = v.size(); ll tem = LLONG_MAX; for (ll i = 1; i < m; ++i){ pre[i] = pre[i - 1] + v[i]; } for (ll i = m - 1; i > 0; --i){ suf[i] = suf[i + 1] + v[i]; } for (ll i = 1; i < m; ++i){ tem = min(tem, v[i] * (i - 1) - pre[i - 1] + suf[i + 1] - v[i] * (m - i - 1)); } if (m == 1) tem = 0; cout << ans + tem; return; } ll ans = 0; vector <pii> v; for (int i = 1; i <= n; ++i){ char p, q; int s, t; cin >> p >> s >> q >> t; if (p == q) ans += abs(s - t); else{ ++ans; //cost to go through a bridge v.pb({s, t}); } } sort(v.begin(), v.end(),[](const auto &i, const auto &j){ return (i.fi + i.se) / 2 < (j.fi + j.se) / 2; }); if (v.empty()){ cout << ans; return; } if (v.size() == 1){ cout << ans + abs(v[0].fi - v[0].se); return; } ll tem = inf; b.resize(2 * v.size() + 1); for (int i = 1; i <= v.size(); ++i){ pre[i] = pre[i - 1] + v[i - 1].fi + v[i - 1].se; } for (int i = 0; i < v.size(); ++i){ b[i * 2 + 1] = v[i].fi; b[i * 2 + 2] = v[i].se; } build(1, b.begin() + 1, b.end(), *min_element(b.begin(), b.end()), *max_element(b.begin(), b.end())); for (int i = 0; i < v.size() - 1; ++i){ ll l = get(i + 1, 1, i * 2 + 2); ll r = get(v.size() - i - 1, i * 2 + 3, v.size() * 2); tem = min(tem, pre[i + 1] - 2 * l + pre[v.size()] - pre[i + 1] - 2 * r); } cout << tem + ans; } #define debu #define taskname "test" signed main(){ if (fopen(taskname".inp", "r")){ freopen(taskname".inp", "r", stdin); #ifdef debug freopen(taskname".out", "w", stdout); #endif } faster; ll tt = 1; //cin >> tt; while (tt--){ Init(); } if (fopen("timeout.txt", "r")){ ofstream timeout("timeout.txt"); timeout << 1000 * double(clock()) / CLOCKS_PER_SEC; #ifndef debug cerr << "\nTime elapsed: " << 1000 * double(clock()) / CLOCKS_PER_SEC << "ms\n"; #endif } }

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

bridge.cpp:47:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   47 | void build(int id, auto i, auto j, int l, int r){
      |                    ^~~~
bridge.cpp:47:28: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   47 | void build(int id, auto i, auto j, int l, int r){
      |                            ^~~~
bridge.cpp: In function 'll get(int, int, int)':
bridge.cpp:80:13: warning: unused variable 'mid' [-Wunused-variable]
   80 |         int mid = (l + r) / 2;
      |             ^~~
bridge.cpp: In function 'void Init()':
bridge.cpp:155:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |     for (int i = 1; i <= v.size(); ++i){
      |                     ~~^~~~~~~~~~~
bridge.cpp:158:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |     for (int i = 0; i < v.size(); ++i){
      |                     ~~^~~~~~~~~~
bridge.cpp:163:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |     for (int i = 0; i < v.size() - 1; ++i){
      |                     ~~^~~~~~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:175:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  175 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...