#include <bits/stdc++.h>
#define pii pair<long long, long long>
#define x first
#define y second
using namespace std;
const int N = 1e5 + 10;
int k, n;
long long ans, dpl[N], dpr[N], suml, sumr;
vector<pii> v;
priority_queue<long long> L;
priority_queue<long long, vector<long long>, greater<long long>> R;
void add( long long x ) {
int sz = L.size() + R.size();
if( L.empty() || x <= L.top() ) {
//printf("L : %d\n",x);
L.emplace( x );
suml += x, sz++;
while( L.size() > ( sz+1 ) / 2 ) {
//printf("sz1 : %d %lld\n",sz,L.top());
R.emplace( L.top() );
sumr += L.top();
suml -= L.top();
L.pop();
}
}
else {
//printf("R : %d\n",x);
R.emplace( x );
sumr += x, sz++;
while( R.size() > ( sz+1 ) / 2 ) {
//printf("sz2 : %d %lld\n",sz,R.top());
L.emplace( R.top() );
sumr -= R.top();
suml += R.top();
R.pop();
}
}
}
long long process( int idx ) {
//printf("IDX : %d %lld %lld\n",idx,v[idx].x,v[idx].y);
add( v[idx].x ), add( v[idx].y );
int sz = L.size() + R.size();
//printf("L : %d %lld %lld R : %d %lld %lld\n",L.size(),L.top(),suml,R.size(),R.top(),sumr);
long long median = L.size() == ( sz + 1 ) / 2 ? L.top() : R.top();
//printf("%d %d %lld\n",sz,idx,median);
return median * ( L.size() - R.size() ) - suml + sumr;
}
int main()
{
scanf("%d %d",&k,&n);
for( int i = 1 ; i <= n ; i++ ) {
char a, c;
long long b, d;
scanf(" %c %lld %c %lld",&a,&b,&c,&d);
if( b > d ) swap( b, d );
if( a == c ) ans += d - b;
else v.emplace_back( pii( b, d ) );
}
if( v.empty() ) return !printf("%lld",ans);
ans += v.size();
sort( v.begin(), v.end(), [&]( const pii &a, const pii &b ) {
return a.x + a.y < b.x + b.y;
});
for( int i = 1 ; i <= v.size() ; i++ ) dpl[i] = process( i-1 );
L = priority_queue<long long>();
R = priority_queue<long long, vector<long long>, greater<long long>>();
suml = sumr = 0LL;
for( int i = v.size() ; i >= 1 ; i-- ) dpr[i] = process( i-1 );
if( k == 1 ) return !printf("%lld",ans+dpl[v.size()]);
long long tmp = 2e18;
for( int i = 1 ; i < v.size() ; i++ ) tmp = min( tmp, dpl[i] + dpr[i+1] );
printf("%lld",ans+tmp);
return 0;
}
Compilation message
bridge.cpp: In function 'void add(long long int)':
bridge.cpp:20:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while( L.size() > ( sz+1 ) / 2 ) {
~~~~~~~~~^~~~~~~~~~~~~~
bridge.cpp:32:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while( R.size() > ( sz+1 ) / 2 ) {
~~~~~~~~~^~~~~~~~~~~~~~
bridge.cpp: In function 'long long int process(int)':
bridge.cpp:47:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
long long median = L.size() == ( sz + 1 ) / 2 ? L.top() : R.top();
~~~~~~~~~^~~~~~~~~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:68:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for( int i = 1 ; i <= v.size() ; i++ ) dpl[i] = process( i-1 );
~~^~~~~~~~~~~
bridge.cpp:75:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for( int i = 1 ; i < v.size() ; i++ ) tmp = min( tmp, dpl[i] + dpr[i+1] );
~~^~~~~~~~~~
bridge.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&k,&n);
~~~~~^~~~~~~~~~~~~~~
bridge.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c %lld %c %lld",&a,&b,&c,&d);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
256 KB |
Output is correct |
2 |
Correct |
4 ms |
256 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
256 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
12 |
Correct |
54 ms |
7144 KB |
Output is correct |
13 |
Correct |
93 ms |
8748 KB |
Output is correct |
14 |
Correct |
74 ms |
7112 KB |
Output is correct |
15 |
Correct |
56 ms |
4840 KB |
Output is correct |
16 |
Correct |
52 ms |
8040 KB |
Output is correct |
17 |
Correct |
81 ms |
8680 KB |
Output is correct |
18 |
Correct |
60 ms |
7916 KB |
Output is correct |
19 |
Correct |
88 ms |
8656 KB |
Output is correct |
20 |
Correct |
67 ms |
8296 KB |
Output is correct |
21 |
Correct |
84 ms |
8424 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
256 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
256 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
256 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
4 ms |
256 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
4 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
13 |
Correct |
6 ms |
384 KB |
Output is correct |
14 |
Correct |
5 ms |
384 KB |
Output is correct |
15 |
Correct |
5 ms |
384 KB |
Output is correct |
16 |
Correct |
5 ms |
384 KB |
Output is correct |
17 |
Correct |
5 ms |
384 KB |
Output is correct |
18 |
Correct |
5 ms |
384 KB |
Output is correct |
19 |
Correct |
5 ms |
384 KB |
Output is correct |
20 |
Correct |
5 ms |
384 KB |
Output is correct |
21 |
Correct |
5 ms |
384 KB |
Output is correct |
22 |
Correct |
5 ms |
384 KB |
Output is correct |
23 |
Correct |
5 ms |
384 KB |
Output is correct |
24 |
Correct |
6 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
256 KB |
Output is correct |
2 |
Correct |
4 ms |
256 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
4 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
4 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
13 |
Correct |
5 ms |
384 KB |
Output is correct |
14 |
Correct |
5 ms |
384 KB |
Output is correct |
15 |
Correct |
5 ms |
384 KB |
Output is correct |
16 |
Correct |
5 ms |
384 KB |
Output is correct |
17 |
Correct |
5 ms |
384 KB |
Output is correct |
18 |
Correct |
5 ms |
512 KB |
Output is correct |
19 |
Correct |
5 ms |
384 KB |
Output is correct |
20 |
Correct |
5 ms |
384 KB |
Output is correct |
21 |
Correct |
5 ms |
384 KB |
Output is correct |
22 |
Correct |
5 ms |
384 KB |
Output is correct |
23 |
Correct |
5 ms |
384 KB |
Output is correct |
24 |
Correct |
5 ms |
512 KB |
Output is correct |
25 |
Correct |
53 ms |
7148 KB |
Output is correct |
26 |
Correct |
71 ms |
7368 KB |
Output is correct |
27 |
Correct |
88 ms |
8140 KB |
Output is correct |
28 |
Correct |
96 ms |
8792 KB |
Output is correct |
29 |
Correct |
95 ms |
8740 KB |
Output is correct |
30 |
Correct |
56 ms |
4524 KB |
Output is correct |
31 |
Correct |
52 ms |
8040 KB |
Output is correct |
32 |
Correct |
79 ms |
8680 KB |
Output is correct |
33 |
Correct |
59 ms |
7912 KB |
Output is correct |
34 |
Correct |
94 ms |
8824 KB |
Output is correct |
35 |
Correct |
69 ms |
8296 KB |
Output is correct |
36 |
Correct |
84 ms |
8424 KB |
Output is correct |
37 |
Correct |
54 ms |
7272 KB |
Output is correct |