제출 #48021

#제출 시각아이디문제언어결과실행 시간메모리
48021yusufakePalembang Bridges (APIO15_bridge)C++98
49 / 100
19 ms5812 KiB
#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);
  ~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...