제출 #45536

#제출 시각아이디문제언어결과실행 시간메모리
45536dqhungdlPalembang Bridges (APIO15_bridge)C++17
22 / 100
438 ms22640 KiB
#include <bits/stdc++.h> using namespace std; typedef pair<int64_t,int64_t> ii; int64_t k,n,Count=1; ii tree1[200005],tree2[200005]; vector<int64_t> V,mind,maxd; map<int64_t,int64_t> F; void Update1(int64_t idx,int64_t data) { while(idx<=Count) { tree1[idx].first+=data; tree1[idx].second++; idx+=idx&-idx; } } ii Query1(int64_t idx) { ii rs=ii(0,0); while(idx>0) { rs.first+=tree1[idx].first; rs.second+=tree1[idx].second; idx-=idx&-idx; } return rs; } void Update2(int64_t idx,int64_t data) { while(idx>0) { tree2[idx].first+=data; tree2[idx].second++; idx-=idx&-idx; } } ii Query2(int64_t idx) { ii rs=ii(0,0); while(idx<=Count) { rs.first+=tree2[idx].first; rs.second+=tree2[idx].second; idx+=idx&-idx; } return rs; } void Sub1() { char c1,c2; int64_t t1,t2,sum=0; for(int64_t i=1;i<=n;i++) { cin>>c1>>t1>>c2>>t2; if(c1==c2) sum+=abs(t1-t2); else { V.push_back(t1); V.push_back(t2); mind.push_back(min(t1,t2)); maxd.push_back(max(t1,t2)); sum+=abs(t1-t2)+1; } } if(V.size()==0) { cout<<sum; return; } sort(V.begin(),V.end()); F[V[0]]=1; for(int64_t i=1;i<V.size();i++) if(V[i]>V[i-1]) F[V[i]]=++Count; for(int64_t i=0;i<mind.size();i++) Update2(F[mind[i]],mind[i]); for(int64_t i=0;i<maxd.size();i++) Update1(F[maxd[i]],maxd[i]); int64_t res=1e18; for(int64_t i=0;i<V.size();i++) { ii t1=Query1(F[V[i]]-1); ii t2=Query2(F[V[i]]+1); res=min(res,sum+2*(V[i]*t1.second-t1.first+t2.first-V[i]*t2.second)); } cout<<res; } int main() { ios_base::sync_with_stdio(false); //freopen("TEST.INP","r",stdin); cin>>k>>n; if(k==1) Sub1(); }

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

bridge.cpp: In function 'void Sub1()':
bridge.cpp:79:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int64_t i=1;i<V.size();i++)
                     ~^~~~~~~~~
bridge.cpp:82:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int64_t i=0;i<mind.size();i++)
                     ~^~~~~~~~~~~~
bridge.cpp:84:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int64_t i=0;i<maxd.size();i++)
                     ~^~~~~~~~~~~~
bridge.cpp:87:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int64_t i=0;i<V.size();i++)
                     ~^~~~~~~~~
#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...