Submission #456209

#TimeUsernameProblemLanguageResultExecution timeMemory
456209nonsensenonsense1Palembang Bridges (APIO15_bridge)C++17
0 / 100
1 ms332 KiB
#include <cstdio> #include <set> #include <algorithm> #include <vector> const int N = 100000; int n, task; long long pref[N + 1], suf[N + 1]; std::vector<std::pair<int, std::pair<int, int> > > a; void process(long long *to) { std::multiset<int> x, y; long long sx = 0, sy = 0; for (int i = 0; i < (int)a.size(); ++i) { x.insert(a[i].second.first); x.insert(a[i].second.second); sx += a[i].second.first; sx += a[i].second.second; y.insert(*prev(x.end())); sy += *prev(x.end()); sx -= *prev(x.end()); x.erase(prev(x.end())); while (*prev(x.end()) > *y.begin()) { long long p = *prev(x.end()), q = *y.begin(); x.erase(prev(x.end())); y.erase(*y.begin()); x.insert(q); y.insert(p); sx -= p - q; sy += p - q; } to[i + 1] = sy - sx; } } int main() { scanf("%d%d", &task, &n); long long ans_add = 0; for (int i = 0; i < n; ++i) { char type1, type2; int l, r; scanf(" %c%d %c%d", &type1, &l, &type2, &r); if (l > r) std::swap(l, r); if (type1 == type2) ans_add += r - l; else { ++ans_add; a.push_back(std::make_pair(l + r, std::make_pair(l, r))); } } std::sort(a.begin(), a.end()); process(pref); std::reverse(a.begin(), a.end()); process(suf); if (task == 1) printf("%lld\n", ans_add + pref[a.size()]); else { long long ans = ~((long long)1 << 63); for (int i = 0; i <= a.size(); ++i) ans = std::min(ans, pref[i] + suf[(int)a.size() - i]); printf("%lld\n", ans_add + ans); } return 0; }

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:59:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   for (int i = 0; i <= a.size(); ++i) ans = std::min(ans, pref[i] + suf[(int)a.size() - i]);
      |                   ~~^~~~~~~~~~~
bridge.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |  scanf("%d%d", &task, &n);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
bridge.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |   scanf(" %c%d %c%d", &type1, &l, &type2, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...