Submission #48038

#	Time	Username	Problem	Language	Result	Execution time	Memory
48038		yusufake	Jakarta Skyscrapers (APIO15_skyscraper)	C++98	0 / 100	5 ms	3724 KiB

skyscraper

#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 (stderr)

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);
  ~^~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43