제출 #585759

#제출 시각아이디문제언어결과실행 시간메모리
585759messiuuuuuPalembang Bridges (APIO15_bridge)C++14
0 / 100
1 ms340 KiB
#include<bits/stdc++.h> #define task "C" #define ll long long #define ld long double #define fi first #define se second #define pb push_back using namespace std; const int MAXN = 1e5 + 5; const ll INF = 1e18 + 5; int n, k; struct TRoad { char h, o; ll ph, po; }a[MAXN]; ll more = 0; void Input() { cin >> k >> n; for (int i = 1; i <= n; i++) { cin >> a[i].h >> a[i].ph >> a[i].o >> a[i].po; } vector<int> cs; for (int i = 1; i <= n; i++) { if (a[i].h == a[i].o) { more += abs(a[i].ph - a[i].po); } else { cs.pb(i); } } for (int i = 0; i < cs.size(); i++) { a[i + 1] = a[cs[i]]; } n = cs.size(); } int truoc[MAXN]; vector<ll> num; int dif; void NenSo() { for (int i = 1; i <= n; i++) { num.pb(a[i].ph); num.pb(a[i].po); } sort(num.begin(), num.end()); num.erase(unique(num.begin(), num.end()), num.end()); for (int i = 1; i <= n; i++) { a[i].ph = lower_bound(num.begin(), num.end(), a[i].ph) - num.begin() + 1; a[i].po = lower_bound(num.begin(), num.end(), a[i].po) - num.begin() + 1; } dif = num.size(); } struct BIT { vector<ll> fe; int sz; void Init(int _sz) { sz = _sz; fe.clear(); fe.resize(sz + 1); } void add(int p, ll val) { for (; p <= sz; p += p & -p) { fe[p] += val; } } ll get(int r) { ll res = 0; for (; r; r -= r & -r) { res += fe[r]; } return res; } ll get(int l, int r) { return get(r) - get(l - 1); } }; ll prefsum[MAXN]; void Solve() { vector<int> cs(n); iota(cs.begin(), cs.end(), 1); sort(cs.begin(), cs.end(), [](int i, int j) { return a[i].po + a[i].ph < a[j].po + a[j].ph; }); NenSo(); BIT bit[2]; bit[0].Init(dif); bit[1].Init(dif); for (int i = 0; i < cs.size(); i++) { int p = cs[i]; //cout << num[a[p].ph - 1] << ' ' << num[a[p].po - 1] << '\n'; bit[0].add(a[p].po, 1); bit[0].add(a[p].ph, 1); bit[1].add(a[p].po, num[a[p].po - 1]); bit[1].add(a[p].ph, num[a[p].ph - 1]); int l = 1, r = dif; while (l <= r) { int mid = (l + r) / 2; if (bit[0].get(1, mid) >= i) r = mid - 1; else l = mid + 1; } prefsum[i] = -bit[1].get(1, l) + num[l - 1] * bit[0].get(1, l) + bit[1].get(l, dif) - num[l - 1] * bit[0].get(l, dif) + i + 1; //cout << prefsum[i] << '\n'; } bit[0].Init(dif); bit[1].Init(dif); ll res = INF; for (int i = (int)cs.size() - 1; i >= 1; i--) { int p = cs[i]; bit[0].add(a[p].po, 1); bit[0].add(a[p].ph, 1); bit[1].add(a[p].po, num[a[p].po - 1]); bit[1].add(a[p].ph, num[a[p].ph - 1]); int l = 1, r = dif; while (l <= r) { int mid = (l + r) / 2; if (bit[0].get(1, mid) >= (int)cs.size() - i) r = mid - 1; else l = mid + 1; } res = min(res, prefsum[i - 1] + -bit[1].get(1, l) + num[l - 1] * bit[0].get(1, l) + bit[1].get(l, dif) - num[l - 1] * bit[0].get(l, dif) + (int)cs.size() - i); } cout << res + more; } 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); } Input(); Solve(); }

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

bridge.cpp: In function 'void Input()':
bridge.cpp:40:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for (int i = 0; i < cs.size(); i++)
      |                     ~~^~~~~~~~~~~
bridge.cpp: In function 'void Solve()':
bridge.cpp:119:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |     for (int i = 0; i < cs.size(); i++)
      |                     ~~^~~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:172:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  172 |         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...