제출 #48021

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
48021		yusufake	Palembang Bridges (APIO15_bridge)	C++98	49 / 100	19 ms	5812 KiB

bridge

#include<bits/stdc++.h> 
using namespace std; 

#define _ int v, int tl, int tr, int l, int r, int h
#define tm (tl + tr >> 1)
#define sol L[h][v],tl,tm,l,r,h 
#define sag R[h][v],tm+1,tr,l,r,h 

#define mp make_pair 
#define pb push_back 
#define st first 
#define nd second 

typedef long long ll; 
typedef pair < ll , ll > pp; 
const int mod = 1e9 + 7; 
const int N   = 2e5 + 5; 

ll root[2][N],L[2][N*20],R[2][N*20],w,id[2],A[N],a;
ll dp[N],tp[N],W[N];
pp s[2][N*20];
char c1,c2;

pp mrg(pp a, pp b){
	return mp(a.st+b.st , a.nd+b.nd);
}
int up(_, int x){
	if(tl > r || tr < l) return v;
	int nw = ++id[h];
	if(!(tl >= l && tr <= r)) { L[h][nw] = up(sol,x); R[h][nw] = up(sag,x); }
	s[h][nw] = mrg(s[h][v] , mp(x,1)); 
	return nw;
}
pp qry(_){
	if(tl > r || tr < l || !v) return mp(0,0);
	if(tl >= l && tr <= r) return s[h][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[0][mid-1],1,w,m,w,0);
		t = dp[i] + x.st - x.nd*W[m];
		x = qry(root[1][mid],1,w,1,i,1);
		t += x.nd*W[i] - x.st;
        //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 < pp > > 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[x+y].pb(mp(x,y));
        if(M[x+y].size() == 1) A[++a] = 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=a; i ;i--){
		y = A[i];
		for(auto x : M[y]){
			j = lower_bound(W+1 , W+w+1 , x.nd) - W;
			p = up(p,1,w,j,j,1,x.nd);
		}
		root[1][i] = p;
	} root[1][0] = p;
	for(p=0,i=1;i<=a;i++){
        //cout << A[i] << " ";
		y = A[i];
		for(auto x : M[y]){
			j = lower_bound(W+1 , W+w+1 , x.st) - W;
			p = up(p,1,w,j,j,0,x.st);
		}
		root[0][i] = p;
	}
   // puts(" aa");
	root[0][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];
	//cout << k << " " << i << " " << dp[i] << " ss\n";
        }
    }
	
	x=y=0;
	for(i=1;i<=w;i++){
		ll w = W[i];
        x += H[w]*w;
		y += H[w];
        //cout << i << " " << dp[i] + y*W[i] - x << " ans\n";
		ans = min(ans , dp[i] + y*w - x);
	}
	cout << z + (w ? ans + ans : 0);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

bridge.cpp: In function 'int up(int, int, int, int, int, int, int)':
bridge.cpp:5:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm (tl + tr >> 1)
             ~~~^~~
bridge.cpp:6:24: note: in expansion of macro 'tm'
 #define sol L[h][v],tl,tm,l,r,h 
                        ^~
bridge.cpp:30:44: note: in expansion of macro 'sol'
  if(!(tl >= l && tr <= r)) { L[h][nw] = up(sol,x); R[h][nw] = up(sag,x); }
                                            ^~~
bridge.cpp:5:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm (tl + tr >> 1)
             ~~~^~~
bridge.cpp:7:21: note: in expansion of macro 'tm'
 #define sag R[h][v],tm+1,tr,l,r,h 
                     ^~
bridge.cpp:30:66: note: in expansion of macro 'sag'
  if(!(tl >= l && tr <= r)) { L[h][nw] = up(sol,x); R[h][nw] = up(sag,x); }
                                                                  ^~~
bridge.cpp: In function 'pp qry(int, int, int, int, int, int)':
bridge.cpp:5:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm (tl + tr >> 1)
             ~~~^~~
bridge.cpp:6:24: note: in expansion of macro 'tm'
 #define sol L[h][v],tl,tm,l,r,h 
                        ^~
bridge.cpp:37:18: note: in expansion of macro 'sol'
  return mrg( qry(sol) , qry(sag) );
                  ^~~
bridge.cpp:5:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm (tl + tr >> 1)
             ~~~^~~
bridge.cpp:7:21: note: in expansion of macro 'tm'
 #define sag R[h][v],tm+1,tr,l,r,h 
                     ^~
bridge.cpp:37:29: note: in expansion of macro 'sag'
  return mrg( qry(sol) , qry(sag) );
                             ^~~
bridge.cpp: In function 'void f(int, int, int, int)':
bridge.cpp:43:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int op, m = l+r >> 1;
                 ~^~
bridge.cpp: In function 'int main()':
bridge.cpp:65:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
         if(x > y) swap(x,y); z += y-x; 
         ^~
bridge.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; 
                              ^
bridge.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);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp: In function 'void f(int, int, int, int)':
bridge.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: 8 / 8
• Subtask 2: 0 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 0 / 37