#include<bits/stdc++.h>
using namespace std;
#define _ int v, int tl, int tr, int l, int r
#define tm (tl + tr >> 1)
#define sol L[v],tl,tm,l,r
#define sag R[v],tm+1,tr,l,r
#define mp make_pair
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef pair < int , pair<ll,ll> > pp;
const int mod = 1e9 + 7;
const int N = 2e5 + 5;
int root[N],L[N*22],R[N*22],w,nw,A[N],a,J[N];
ll dp[N],tp[N],W[N];
pp s[N*22];
char c1,c2;
pp mrg(pp a, pp b){
return mp(a.st+b.st , mp(a.nd.st+b.nd.st , a.nd.nd+b.nd.nd));
}
int up(_, pair<ll,ll> x){
if(tl > r || tr < l) return v;
int nw = ++nw;
if(!(tl >= l && tr <= r)) { L[nw] = up(sol,x); R[nw] = up(sag,x); }
s[nw] = mrg(s[v] , mp(1,x));
return nw;
}
pp qry(_){
if(tl > r || tr < l || !v) return mp(0,mp(0,0));
if(tl >= l && tr <= r) return s[v];
return mrg( qry(sol) , qry(sag) );
}
void f(int l, int r, int opl, int opr){
if(l > r) return;
ll t;
int op, m = l+r >> 1;
pp x;
for(int i=max(m+1,opl); i<=opr; i++){
int mid = upper_bound(A+1 , A+a+1 , W[m]+W[i]) - A;
x = qry(root[i],1,a,mid,J[i]-1);
t = dp[i] + x.st*W[m] - x.nd.nd;
x = qry(root[i],1,a,J[m],mid-1);
t += x.nd.st - x.st*W[i];
//cout << m << " " << i << " --->>> " << mid << " " << t << " aa\n";
if(tp[m] > t) { tp[m] = t; op = i; }
}
if(l == r) return;
f(l,m-1,opl,op); f(m+1,r,op,opr);
}
map < int , vector<int> > M;
map < int , ll > H,H2;
ll n,k,i,j,p,x,y,z,ans = 1LL << 55;
int main(){
cin >> k >> n;
for(i=1;i<=n;i++){
scanf(" %c%lld %c%lld",&c1,&x,&c2,&y);
if(x > y) swap(x,y); z += y-x;
if(c1 == c2) continue;
z++;
H[y]++;
M[y].pb(x);
A[i] = x+y;
if(!H2[x]) { H2[x] = 1; W[++w] = x; }
if(!H2[y]) { H2[y] = 1; W[++w] = y; }
}
sort(W+1 , W+w+1);
sort(A+1 , A+a+1);
for(p=0,i=1;i<=w;i++){
y = W[i];
for(auto x : M[y]){
j = lower_bound(A+1 , A+a+1 , y+x) - A;
p = up(p,1,a,j,j,mp(x,y));
}
root[i] = p;
J[i] = lower_bound(A+1 , A+a+1 , y+y) - A;
}
root[a+1] = p;
memset(dp , 22 , sizeof dp);
W[w+1] = 1LL << 55;
dp[w+1] = 0;
for(; k-- ;){
memset(tp , 22 , sizeof tp);
f(1,w,1,w+1);
for(i=1;i<=w;i++) dp[i] = tp[i];
}
x=y=0;
for(i=1;i<=w;i++){
ll w = W[i];
x += H[w]*w;
y += H[w];
ans = min(ans , dp[i] + y*w - x);
}
cout << z + (w ? ans : 0);
return 0;
}
Compilation message
skyscraper.cpp: In function 'int up(int, int, int, int, int, std::pair<long long int, long long int>)':
skyscraper.cpp:29:11: warning: operation on 'nw' may be undefined [-Wsequence-point]
int nw = ++nw;
^~~~
skyscraper.cpp:5:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
#define tm (tl + tr >> 1)
~~~^~~
skyscraper.cpp:6:21: note: in expansion of macro 'tm'
#define sol L[v],tl,tm,l,r
^~
skyscraper.cpp:30:41: note: in expansion of macro 'sol'
if(!(tl >= l && tr <= r)) { L[nw] = up(sol,x); R[nw] = up(sag,x); }
^~~
skyscraper.cpp:5:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
#define tm (tl + tr >> 1)
~~~^~~
skyscraper.cpp:7:18: note: in expansion of macro 'tm'
#define sag R[v],tm+1,tr,l,r
^~
skyscraper.cpp:30:60: note: in expansion of macro 'sag'
if(!(tl >= l && tr <= r)) { L[nw] = up(sol,x); R[nw] = up(sag,x); }
^~~
skyscraper.cpp: In function 'pp qry(int, int, int, int, int)':
skyscraper.cpp:5:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
#define tm (tl + tr >> 1)
~~~^~~
skyscraper.cpp:6:21: note: in expansion of macro 'tm'
#define sol L[v],tl,tm,l,r
^~
skyscraper.cpp:37:18: note: in expansion of macro 'sol'
return mrg( qry(sol) , qry(sag) );
^~~
skyscraper.cpp:5:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
#define tm (tl + tr >> 1)
~~~^~~
skyscraper.cpp:7:18: note: in expansion of macro 'tm'
#define sag R[v],tm+1,tr,l,r
^~
skyscraper.cpp:37:29: note: in expansion of macro 'sag'
return mrg( qry(sol) , qry(sag) );
^~~
skyscraper.cpp: In function 'void f(int, int, int, int)':
skyscraper.cpp:43:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int op, m = l+r >> 1;
~^~
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:65:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if(x > y) swap(x,y); z += y-x;
^~
skyscraper.cpp:65:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
if(x > y) swap(x,y); z += y-x;
^
skyscraper.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c%lld %c%lld",&c1,&x,&c2,&y);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp: In function 'int up(int, int, int, int, int, std::pair<long long int, long long int>)':
skyscraper.cpp:29:13: warning: 'nw' may be used uninitialized in this function [-Wmaybe-uninitialized]
int nw = ++nw;
^~
skyscraper.cpp: In function 'void f(int, int, int, int)':
skyscraper.cpp:55:3: warning: 'op' may be used uninitialized in this function [-Wmaybe-uninitialized]
f(l,m-1,opl,op); f(m+1,r,op,opr);
~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
3448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
3688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
3688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
3688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
3724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
