#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
using pii = pair<int,int>;
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
const int maxn = (int)1e5+10;
const int LINF = (int)1e18;
vector<int> v;
vector<pii> seg;
set<pii> bef,dur,aft;
int t, n, tot, ans=LINF;
int a[maxn], b[maxn];
priority_queue<int> p1;
priority_queue<int,vector<int>,greater<int>> p2;
int sum, x;
void adjust(){
while(!p1.empty() and sz(p1)>sz(p2))
x=p1.top(), p1.pop(),p2.push(x), sum+=2*x;
while(!p2.empty() and sz(p1)<sz(p2))
x=p2.top(), p2.pop(),p1.push(x), sum-=2*x;
}
void add(int x){
if(p1.empty() or p1.top()>=x) p1.push(x), sum-=x;
else p2.push(x), sum+=x; adjust();
}
void chk(int a[]){
while(!p1.empty())p1.pop(); while(!p2.empty())p2.pop(); sum=0;
for(int i = 0; i < sz(seg); i++)
add(seg[i].se), add(seg[i].fi-seg[i].se), a[i]=sum;
}
int32_t main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> t >> n; int ans = LINF;
for(int i = 0; i < n; i++){
char a, c; int b, d;
cin >> a >> b >> c >> d;
if(a==c) tot+=abs(b-d);
else seg.pb({b+d, min(b,d)}), tot++;
}
sort(all(seg));
if(!seg.empty()) chk(a), ans=a[sz(seg)-1];
if(t==2){
chk(a),reverse(all(seg)),chk(b);
for(int i = 0; i < sz(seg); i++)
ans = min(ans, a[i]+b[sz(seg)-i-2]);
}
if(seg.empty()) ans=0;
cout << ans+tot;
}
Compilation message
bridge.cpp: In function 'void add(long long int)':
bridge.cpp:30:2: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
30 | else p2.push(x), sum+=x; adjust();
| ^~~~
bridge.cpp:30:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
30 | else p2.push(x), sum+=x; adjust();
| ^~~~~~
bridge.cpp: In function 'void chk(long long int*)':
bridge.cpp:34:2: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
34 | while(!p1.empty())p1.pop(); while(!p2.empty())p2.pop(); sum=0;
| ^~~~~
bridge.cpp:34:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
34 | while(!p1.empty())p1.pop(); while(!p2.empty())p2.pop(); sum=0;
| ^~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
352 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
216 KB |
Output is correct |
2 |
Correct |
0 ms |
216 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
26 ms |
5580 KB |
Output is correct |
13 |
Correct |
52 ms |
5300 KB |
Output is correct |
14 |
Correct |
40 ms |
5828 KB |
Output is correct |
15 |
Correct |
28 ms |
3536 KB |
Output is correct |
16 |
Correct |
33 ms |
5508 KB |
Output is correct |
17 |
Correct |
35 ms |
5576 KB |
Output is correct |
18 |
Correct |
39 ms |
5524 KB |
Output is correct |
19 |
Correct |
44 ms |
5676 KB |
Output is correct |
20 |
Correct |
34 ms |
5556 KB |
Output is correct |
21 |
Correct |
41 ms |
5500 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
216 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
328 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
216 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
216 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
344 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
2 ms |
328 KB |
Output is correct |
20 |
Correct |
2 ms |
340 KB |
Output is correct |
21 |
Correct |
2 ms |
340 KB |
Output is correct |
22 |
Correct |
2 ms |
340 KB |
Output is correct |
23 |
Correct |
2 ms |
340 KB |
Output is correct |
24 |
Correct |
2 ms |
336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
216 KB |
Output is correct |
2 |
Correct |
0 ms |
216 KB |
Output is correct |
3 |
Correct |
0 ms |
216 KB |
Output is correct |
4 |
Correct |
1 ms |
216 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
2 ms |
348 KB |
Output is correct |
15 |
Correct |
2 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
344 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
2 ms |
340 KB |
Output is correct |
20 |
Correct |
2 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
58 ms |
7100 KB |
Output is correct |
26 |
Correct |
100 ms |
7404 KB |
Output is correct |
27 |
Correct |
132 ms |
8628 KB |
Output is correct |
28 |
Correct |
139 ms |
9192 KB |
Output is correct |
29 |
Correct |
137 ms |
9272 KB |
Output is correct |
30 |
Correct |
70 ms |
4900 KB |
Output is correct |
31 |
Correct |
71 ms |
8000 KB |
Output is correct |
32 |
Correct |
98 ms |
8656 KB |
Output is correct |
33 |
Correct |
92 ms |
8244 KB |
Output is correct |
34 |
Correct |
106 ms |
8708 KB |
Output is correct |
35 |
Correct |
66 ms |
8196 KB |
Output is correct |
36 |
Correct |
106 ms |
8412 KB |
Output is correct |
37 |
Correct |
57 ms |
7148 KB |
Output is correct |