제출 #509824

#제출 시각아이디문제언어결과실행 시간메모리
509824sam571128Palembang Bridges (APIO15_bridge)C++17
22 / 100
531 ms21188 KiB
#include <bits/stdc++.h> #include <bits/extc++.h> #define int long long #define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; using namespace __gnu_pbds; const int N = 2e5+5; pair<int,int> bit[N]; int now[N]; pair<int,int> operator + (pair<int,int> a, pair<int,int> b){ return {a.first+b.first,a.second+b.second}; } pair<int,int> operator - (pair<int,int> a, pair<int,int> b){ return {a.first-b.first,a.second-b.second}; } void update(int pos, pair<int,int> val){ while(pos < N){ bit[pos] = bit[pos] + val; pos += pos&-pos; } } pair<int,int> query(int pos){ pair<int,int> res = {0,0}; while(pos){ res = res + bit[pos]; pos -= pos&-pos; } return res; } typedef tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; int t; signed main(){ fastio int k, n; cin >> k >> n; vector<int> tmp; int ans = 1e18, anstmp = 0; vector<pair<int,int>> v; for(int i = 0;i < n;i++){ char a,b; int x,y; cin >> a >> x >> b >> y; if(a == b) anstmp += abs(x-y); else{ anstmp++; tmp.push_back(x); tmp.push_back(y); v.push_back({x,y}); } } sort(tmp.begin(),tmp.end()); sort(v.begin(),v.end(),[&](auto a, auto b){ return a.first+a.second < b.first+b.second; }); ordered_set s; for(int i = 0;i < v.size();i++){ auto [x,y] = v[i]; s.insert({x,t++}); s.insert({y,t++}); update(lower_bound(tmp.begin(),tmp.end(),x)-tmp.begin()+1,{1,x}); update(lower_bound(tmp.begin(),tmp.end(),y)-tmp.begin()+1,{1,y}); int med = (*s.find_by_order(s.size()/2)).first; pair<int,int> q1 = query(N-1)-query(lower_bound(tmp.begin(),tmp.end(),med)-tmp.begin()+1), q2 = query(lower_bound(tmp.begin(),tmp.end(),med)-tmp.begin()); now[i] = (q1.second-med*q1.first) + (med*q2.first-q2.second); } s.clear(); fill(bit,bit+N,make_pair(0,0)); for(int i = v.size()-1;i >= 1;i--){ auto [x,y] = v[i]; s.insert({x,t++}); s.insert({y,t++}); update(lower_bound(tmp.begin(),tmp.end(),x)-tmp.begin()+1,{1,x}); update(lower_bound(tmp.begin(),tmp.end(),y)-tmp.begin()+1,{1,y}); int med = (*s.find_by_order(s.size()/2)).first; pair<int,int> q1 = query(N-1)-query(lower_bound(tmp.begin(),tmp.end(),med)-tmp.begin()+1), q2 = query(lower_bound(tmp.begin(),tmp.end(),med)-tmp.begin()); ans = min(ans,now[i-1]+(q1.second-med*q1.first) + (med*q2.first-q2.second)); } if(k==1){ cout << now[v.size()-1] + anstmp << "\n"; }else{ cout << ans+anstmp << "\n"; } }

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

bridge.cpp: In function 'int main()':
bridge.cpp:72:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(int 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...