제출 #918961

#제출 시각아이디문제언어결과실행 시간메모리
918961phamducminhPalembang Bridges (APIO15_bridge)C++17
22 / 100
78 ms11288 KiB
//******************/ //* I<3 C++ */ //* I WANT ANY AC */ //* I LOVE PROGRAM!*/ //*IT'S long longERESTING*/ //* I LOVE PROGRAM!*/ //* IN CONTESTS */ //* GET SCORE */ //* AC CODE */ //* LET'S */ //* GO */ //* Written by: */ //* Duc Minh */ #include <bits/stdc++.h> #include <iostream> #include <cmath> #include <vector> #include <map> #include <set> #include <stack> #include <algorithm> #include <string> #include <queue> #include <cctype> #include <cstring> #include <iomanip> #include <deque> // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/tree_policy.hpp> using namespace std; // using namespace __gnu_pbds; #define file(name) freopen(name".inp", "r", stdin);\ freopen(name".out", "w", stdout); #define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update> #define TIME (1.0 * clock() / CLOCKS_PER_SEC) #define all(a) a.begin(),a.end() #define endl "\n" #define all1(a) a+1,a+n+1 // #define unordered_map map // #define push_back emplace_back // #define gcd(a,b) __gcd(a,b); // #define lcm(a,b) (a*b)/gcd(a,b); const long long INF = (long long)1e18; const long long MOD = (long long)1e9+7; const long long MODD = 1e9; /// 998244353 const long long maxN = 25009; ///-------------------------------- void solve(); signed main(){ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); // file("tbrackets"); long long t; // cin >> t; t=1; while (t--){ solve(); } cerr << "Time elapsed: " << TIME << "s.\n"; cerr << "ducminh" << "\n"; return 0; } ///--------------------[PROBLEM SOLUTION]--------------------/// multiset<long long> ss; struct Compare { bool operator() (const long long& a, const long long& b) const { return a > b; } }; long long n,k,a[200009],pre[200009],suf[200009]; multiset<long long,Compare> down; multiset<long long> up; long long sum=0,sum1=0,ans=0,sum2=0; vector<pair<long long,long long>> pp; void sub1(){ ans=0; auto it=ss.begin(); if (ss.size()==0) return cout << sum2, void(); advance(it, ss.size()/2); long long tam=*it; for (long long x: ss){ ans+=abs(tam-x); } ans+=(ss.size()/2); ans+=sum2; cout << ans; } void sub2(){ if (ss.size()==0) return cout << sum2, void(); vector<int> luu; for (int x: ss) luu.push_back(x); // down.insert(a[0]); // cout << for (long long i=0; i<luu.size(); i++){ // if (a[i-k]<*up.begin()) {if (down.size()) down.erase(down.find(a[i-k]));} // else {if (up.size()) up.erase(up.find(a[i-k]));} // cout << i << ' ' << a[i-k] << "\n"; if (luu[i]<*up.begin() || up.size()==0) down.insert(luu[i]); else up.insert(luu[i]); if (down.size()-up.size()==3){ long long tam=*down.begin(); down.erase(down.begin()); up.insert(tam); } if (down.size()-up.size()==2) { up.insert(*down.begin()); down.erase(down.begin()); } if (up.size()>down.size()){ long long tam=*up.begin(); up.erase(up.begin()); down.insert(tam); } pre[i]=*down.begin(); // cout << i << ':'; // for (long long x: down) cout << x << ' '; // cout << "\n"; // for (long long x: up) cout << x << ' '; // cout << "\n"; } down.clear(); up.clear(); for (long long i=luu.size()-1; i>=0; i--){ // if (a[i-k]<*up.begin()) {if (down.size()) down.erase(down.find(a[i-k]));} // else {if (up.size()) up.erase(up.find(a[i-k]));} // cout << i << ' ' << a[i-k] << "\n"; if (luu[i]<*up.begin() || up.size()==0) down.insert(luu[i]); else up.insert(luu[i]); if (down.size()-up.size()==3){ long long tam=*down.begin(); down.erase(down.begin()); up.insert(tam); } if (down.size()-up.size()==2) { up.insert(*down.begin()); down.erase(down.begin()); } if (up.size()>down.size()){ long long tam=*up.begin(); up.erase(up.begin()); down.insert(tam); } suf[i]=*down.begin(); // cout << i << ':'; // for (long long x: down) cout << x << ' '; // cout << "\n"; // for (long long x: up) cout << x << ' '; // cout << "\n"; } ans=INF; for (int i=0; i<luu.size()-1; i++){ long long tamans=0; for (int j=0; j<pp.size(); j++){ long long aa = pp[j].first, bb = pp[j].second; tamans+=min(abs(aa-pre[i])+abs(bb-pre[i]), abs(aa-suf[i+1])+abs(bb-suf[i+1])); } ans=min(ans,tamans); } ans+=(ss.size()/2); ans+=sum2; cout << ans; } void solve(){ long long k,n; cin >> k >> n; for (long long i=1; i<=n; i++){ char ch1,ch2; long long x,y; cin >> ch1 >> x >> ch2 >> y; if (ch1!=ch2) { ss.insert(x); ss.insert(y); pp.push_back({x, y}); sum+=x+y; } else sum1+=2,sum2+=abs(y-x); // pp.push_back({x, y}); } if (k==1) sub1(); else sub2(); }

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

bridge.cpp: In function 'void sub2()':
bridge.cpp:164:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |         for (long long i=0; i<luu.size(); i++){
      |                             ~^~~~~~~~~~~
bridge.cpp:247:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  247 |         for (int i=0; i<luu.size()-1; i++){
      |                       ~^~~~~~~~~~~~~
bridge.cpp:250:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  250 |             for (int j=0; j<pp.size(); j++){
      |                           ~^~~~~~~~~~
#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...