이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define N 1000001
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll INF = 1e18, MOD = 1e9 + 7, MOD2 = 1e6 + 3;
int n, k, median;
ll side = 0, lsum = 0, rsum = 0;
ll pr[N];
priority_queue <int> l, r;
struct seg {
int l, r;
bool operator < (const seg& b) {
return l + r < b.l + b.r;
}
};
vector <seg> v;
void insert (int x) {
if (!l.size ()) {
median = x;
l.push (x);
lsum += x;
return;
}
if (x <= median) { l.push (x), lsum += x; }
else { r.push (-x), rsum += x; }
int len = (l.size () + r.size () + 1) / 2;
if (l.size () > len) {
int k = l.top ();
l.pop ();
r.push (-k);
lsum -= k, rsum += k;
}
if (l.size () < len) {
int k = -r.top ();
r.pop ();
l.push (k);
lsum += k, rsum -= k;
}
median = l.top ();
}
int main () {
cin >> k >> n;
for (int i = 0; i < n; i++) {
string a, b;
int la, lb;
cin >> a >> la >> b >> lb;
if (a == b) side += abs (la - lb);
else v.push_back ({la, lb});
}
sort (v.begin (), v.end ());
for (int i = 0; i < v.size (); i++) {
insert (v[i].l), insert (v[i].r);
pr[i] = rsum - lsum;
}
if (k == 2) {
lsum = 0, rsum = 0;
while (!l.empty ()) l.pop ();
while (!r.empty ()) r.pop ();
ll mx = INF;
for (int i = v.size () - 1; i >= 0; i--) {
insert (v[i].l), insert (v[i].r);
mx = min (mx, rsum - lsum + (i ? pr[i-1] : 0));
}
cout << mx + side + v.size ();
}
else cout << pr[v.size ()-1] + side + v.size ();
}
컴파일 시 표준 에러 (stderr) 메시지
bridge.cpp: In function 'void insert(int)':
bridge.cpp:43:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (l.size () > len) {
~~~~~~~~~~^~~~~
bridge.cpp:50:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (l.size () < len) {
~~~~~~~~~~^~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:74:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < v.size (); i++) {
~~^~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |