제출 #585532

#제출 시각아이디문제언어결과실행 시간메모리
585532Tien_NoobPalembang Bridges (APIO15_bridge)C++17
63 / 100
220 ms38848 KiB
//Make CSP great again //Vengeance #include <bits/stdc++.h> #define TASK "TESTCODE" #define Log2(x) 31 - __builtin_clz(x) using namespace std; const int N = 1e5; int k, n; long long add, res = 1e18; set<int> pos; multiset<pair<int, int> > L, mid, R; long long sum[3]; map<int, int> comp; long long t[N + 1]; int cnt[2]; struct FenwickTree { long long tree[N + 1]; void add(int pos, int val) { for (; pos <= N; pos += (pos & -pos)) { tree[pos] += val; } } long long sum(int pos) { long long ret = 0; for (; pos > 0; pos -= (pos & -pos)) { ret += tree[pos]; } return ret; } long long sum(int l, int r) { return sum(r) - sum(l - 1); } } tree[4]; void read() { cin >> k >> n; while(n--) { char P, Q; int s, t; cin >> P >> s >> Q >> t; if (P == Q) { add += abs(s - t); continue; } pos.insert(s); pos.insert(t); if (s > t) { swap(s, t); } L.insert({s, t}); //R.insert({t, s}); ++cnt[1]; sum[1] += s + t; ++add; } } vector<pair<int, int> > point; long long Get(int i, int sz) { int low = 1, high = N; while(low <= high) { int mid = (low + high)/2; if (tree[i].sum(mid) >= sz) { high = mid - 1; } else { low = mid + 1; } } long long ret = t[low] * tree[i].sum(low - 1) - tree[i + 1].sum(low - 1) + tree[i + 1].sum(low + 1, N) - tree[i].sum(low + 1, N) * t[low]; assert(ret >= 0); //cerr << t[low] << ' ' << ret << ' '; return ret; } void solve() { if (pos.empty()) { cout << add; return ; } if (k == 1) { for (int x : pos) { while(!L.empty() && L.begin()->first <= x) { sum[2] += L.begin()->second - L.begin()->first; --cnt[1]; sum[1] -= L.begin()->first + L.begin()->second; mid.insert({L.begin()->second, L.begin()->first}); L.erase(L.begin()); } while(!mid.empty() && mid.begin()->first <= x) { ++cnt[0]; sum[0] += mid.begin()->first + mid.begin()->second; sum[2] -= mid.begin()->first - mid.begin()->second; mid.erase(mid.begin()); } res = min(res, 2LL * x * cnt[0] - sum[0] + sum[1] - 2LL * cnt[1] * x + sum[2]); } cout << res + add; return ; } int j = 0; for (auto &p : pos) { comp[p] = ++j; t[j] = p; } for (auto &p : L) { point.emplace_back(p.first, p.second); tree[2].add(comp[p.first], 1); tree[2].add(comp[p.second], 1); tree[3].add(comp[p.first], p.first); tree[3].add(comp[p.second], p.second); } sort(point.begin(), point.end(), [&](auto &x, auto &y) { return x.first + x.second < y.first + y.second; }); for (int i = 0; i < point.size(); ++ i) { res = min(res, Get(0, i) + Get(2, point.size() - i)); tree[2].add(comp[point[i].first], -1); tree[2].add(comp[point[i].second], -1); tree[3].add(comp[point[i].first], -point[i].first); tree[3].add(comp[point[i].second], -point[i].second); tree[0].add(comp[point[i].first], 1); tree[0].add(comp[point[i].second], 1); tree[1].add(comp[point[i].first], point[i].first); tree[1].add(comp[point[i].second], point[i].second); //cerr << '\n'; } cout << res + add; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); if (fopen(TASK".INP", "r")) { freopen(TASK".INP", "r", stdin); //freopen(TASK".OUT", "w", stdout); } int t = 1; bool typetest = false; if (typetest) { cin >> t; } for (int __ = 1; __ <= t; ++ __) { //cout << "Case " << __ << ": "; read(); solve(); } }

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

bridge.cpp: In function 'void solve()':
bridge.cpp:136: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]
  136 |     for (int i = 0; i < point.size(); ++ i)
      |                     ~~^~~~~~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:158:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |         freopen(TASK".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...