제출 #119479

#제출 시각아이디문제언어결과실행 시간메모리
119479Charis02Palembang Bridges (APIO15_bridge)C++14
0 / 100
3 ms640 KiB
#include<iostream> #include<stdio.h> #include<vector> #include<cmath> #include<queue> #include<utility> #include<string.h> #include<map> #include<set> #include<algorithm> #define ll long long #define pi pair < ll,ll > #define mp(a,b) make_pair(a,b) #define rep(i,a,b) for(int i = a;i < b;i++) #define N 100004 #define INF 1e16 using namespace std; ll n,k; pi ar[N]; ll b,d; char a,c; ll ans,cnt; map < ll,ll > telionei; map < ll,ll > arxizei; set < ll > p; ll checkbridge(ll x) { ll bridge = x; ll res = ans; rep(j,0,cnt) { if(ar[j].first <= bridge && bridge <= ar[j].second) continue; else if(bridge < ar[j].first) res += 2*(ar[j].first - bridge); else res += 2*(bridge-ar[j].second); } return res; } int main() { ios_base::sync_with_stdio(false); cin >> k >> n; rep(i,0,n) { cin >> a >> b >> c >> d; if(d < b) swap(b,d); ans += d-b; if(a != c) { ar[cnt].first = b; arxizei[b]++; ar[cnt].second = d; telionei[d]++; ans++; cnt++; } } if(cnt == 0) { cout << ans; return 0; } rep(i,0,cnt) { p.insert(ar[i].first); p.insert(ar[i].second); } vector < ll > possible; for(set < ll >::iterator it = p.begin();it != p.end();it++) { possible.push_back(*it); } ll low = 0; ll high = possible.size()-1; ll res = 0; while(low <= high) { ll mid = (low+high)/2; if(checkbridge(mid-1) >= checkbridge(mid)) { low = mid+1; res = mid; } else { high = mid-1; } } cout << checkbridge(res); return 0; ll fin = INF; ll aristera = 0; ll bridge = possible[0]; res = ans; ll deksia = 0; rep(i,0,cnt) { if(ar[i].first < bridge && bridge < ar[i].second) continue; else if(bridge < ar[i].first) { deksia++; res += 2*(ar[i].first - bridge); } else { aristera++; res += 2*(bridge-ar[i].second); } } fin = res; // cout << res << endl; rep(i,1,possible.size()) { res += 2*aristera*(possible[i] - possible[i-1]); res -= 2*deksia*(possible[i] - possible[i-1]); bridge = possible[i]; // cout << bridge << " " << res << " " << deksia << " " << aristera << endl; aristera += telionei[bridge]; deksia -= arxizei[bridge]; fin = min(fin,res); } cout << fin; return 0; } /* 1 5 B 0 A 4 B 1 B 3 A 5 B 7 B 2 A 6 B 1 A 7 1 3 A 1 B 1 A 4 B 7 A 10 B 12 */

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

bridge.cpp: In function 'int main()':
bridge.cpp:14:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i = a;i < b;i++)
bridge.cpp:139:9:
     rep(i,1,possible.size())
         ~~~~~~~~~~~~~~~~~~~         
bridge.cpp:139:5: note: in expansion of macro 'rep'
     rep(i,1,possible.size())
     ^~~
#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...