제출 #585540

#제출 시각아이디문제언어결과실행 시간메모리
585540HuyPalembang Bridges (APIO15_bridge)C++17
0 / 100
1 ms340 KiB
#include<bits/stdc++.h> //#define int long long #define pii pair<int,ll> //#define fi first //#define se second /*#pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma")*/ using namespace std; using ll = long long; using ull = unsigned long long; using ldb = long double; const ll N = (int)1e9 + 1; const int maxN = (int)1e6 + 1; const int mod = 1e9 + 7; //const int mod = 998244353; const ll infty = 1e18 + 7; const int base = (int)4e5; void InputFile() { //freopen("scrivener.inp","r",stdin); //freopen("scrivener.out","w",stdout); //freopen("test.out","r",stdin); } void FastInput() { ios_base::sync_with_stdio(false); cin.tie(nullptr); } int k,n; char P[maxN],Q[maxN]; int S[maxN],T[maxN]; vector<pii> vc; int dak = 0; int su = 0; vector<int> save; map<int,int> n_val; vector<int> oval; int var; bool FA(pii a,pii b) { return a.first + a.second < b.first + b.second; } int idbit[2][maxN]; ll sumbit[2][maxN]; void Updateid(int t,int idx,int val) { while(idx <= 2 * n) { idbit[t][idx] += val; idx += (idx & (-idx)); } } int Getid(int t,int idx) { int res = 0; while(idx > 0) { res += idbit[t][idx]; idx -= (idx & (-idx)); } return res; } void Updatesum(int t,int idx,int val) { while(idx <= 2 * n) { sumbit[t][idx] += val; idx += (idx & (-idx)); } } int Getsum(int t,int idx) { int res = 0; while(idx > 0) { res += sumbit[t][idx]; idx -= (idx & (-idx)); } return res; } void Read() { cin >> k >> n; for(int i = 1; i <= n; i++) { cin >> P[i] >> S[i] >> Q[i] >> T[i]; if(P[i] != Q[i]) { if(S[i] > T[i]) swap(S[i],T[i]); vc.push_back({S[i],T[i]}); dak++; } else { su += abs(S[i]-T[i]); } } } void Renumb() { sort(save.begin(),save.end()); int old = -1; int now = 0; oval.push_back(-1); for(int i : save) { if(i > old) { old = i; now++; oval.push_back(i); } n_val[old] = now; } var = now; } void Solve() { if(vc.empty()) { cout << su; return; } sort(vc.begin(),vc.end(),FA); for(pii tmp : vc) { save.push_back(tmp.first); save.push_back(tmp.second); } Renumb(); for(pii tmp : vc) { Updateid(1,n_val[tmp.first],1); Updateid(1,n_val[tmp.second],1); Updatesum(1,n_val[tmp.first],tmp.first); Updatesum(1,n_val[tmp.second],tmp.second); } ll res = infty; int low = 1; int high = var; ll check = 0; while(low <= high) { int mid = (low + high) / 2; if(Getid(1,mid) > (int)vc.size()) high = mid - 1; else low = mid + 1; } check += oval[low] * Getid(1,low) - Getsum(1,low); check += (Getsum(1,2*n) - Getsum(1,low)) - oval[low] * (Getid(1,2*n)-Getid(1,low)); res = min(res,check); for(int i = 0; i < vc.size(); i++) { Updateid(1,n_val[vc[i].first],-1); Updateid(0,n_val[vc[i].first],1); Updateid(1,n_val[vc[i].second],-1); Updateid(0,n_val[vc[i].second],1); Updatesum(1,n_val[vc[i].first],-vc[i].first); Updatesum(0,n_val[vc[i].first],vc[i].first); Updatesum(1,n_val[vc[i].second],-vc[i].second); Updatesum(0,n_val[vc[i].second],vc[i].second); ll check = 0; /// med part1 int low = 1; int high = var; while(low <= high) { int mid = (low + high) / 2; if(Getid(0,mid) > i + 1) high = mid - 1; else low = mid + 1; } check += oval[low] * Getid(0,low) - Getsum(0,low); check += (Getsum(0,2*n) - Getsum(0,low)) - oval[low] * (Getid(0,2*n)-Getid(0,low)); /// med part 2 if(i != vc.size() - 1) { low = 1; high = var; while(low <= high) { int mid = (low + high) / 2; if(Getid(1,mid) > (int)vc.size()-1-i) high = mid - 1; else low = mid + 1; } check += oval[low] * Getid(1,low) - Getsum(1,low); check += (Getsum(1,2*n) - Getsum(1,low)) - oval[low] * (Getid(1,2*n)-Getid(1,low)); } res = min(res,check); } cout << res + su + dak; } void Debug() { } int32_t main() { FastInput(); //InputFile(); //int sub_type; //cin >> sub_type; //Sieve(); //Prepare(); int test; //cin >> test; test = 1; while(test--) //for(int prc = 1; prc <= test; prc++) { Read(); Solve(); //Debug(); } } /* 2 5 B 0 A 4 B 1 B 3 A 5 B 7 B 2 A 6 B 1 A 7 */

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

bridge.cpp: In function 'void Solve()':
bridge.cpp:171:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |     for(int i = 0; i < vc.size(); i++)
      |                    ~~^~~~~~~~~~~
bridge.cpp:200:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  200 |         if(i != vc.size() - 1)
      |            ~~^~~~~~~~~~~~~~~~
#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...