제출 #919407

#제출 시각아이디문제언어결과실행 시간메모리
919407phamducminhPalembang Bridges (APIO15_bridge)C++17
22 / 100
109 ms13668 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; } int suml=0, sumr=0; inline void push(int val){ if (val<*up.begin() || up.size()==0) down.insert(val),suml+=val; else up.insert(val),sumr+=val; if (down.size()-up.size()==3){ long long tam=*down.begin(); down.erase(down.find(tam)); suml-=tam; sumr+=tam; up.insert(tam); } if (down.size()-up.size()==2) { long long tam=*down.begin(); up.insert(*down.begin()); suml-=tam; sumr+=tam; down.erase(down.find(tam)); } if (up.size()>down.size()){ long long tam=*up.begin(); up.erase(up.find(tam)); suml+=tam; sumr-=tam; down.insert(tam); } } inline int get(){ int tam=*down.begin(); return (sumr - 1LL*tam*up.size()) + (1LL*tam*down.size() - suml); } void sub2(){ if (ss.size()==0) return cout << sum2, void(); vector<long long> luu; for (long long x: ss) luu.push_back(x); for (long long i=0; i<pp.size(); i++){ push(pp[i].first); push(pp[i].second); pre[i]=get(); } // 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"; // } // for (long long i=0; i<luu.size(); i++){ // cout << luu[i] << ' ' << pre[i] << "\n"; // } down.clear(); up.clear(); suml=0; sumr=0; for (long long i=pp.size()-1; i>=0; i--){ push(pp[i].first); push(pp[i].second); suf[i]=get(); } // 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"; // } // for (long long i=0; i<pp.size(); i++){ // cout << i << ' ' << suf[i] << "\n"; // } // cout << pre[pp.size()-1]+(luu.size()/2)+sum2 << "\n"; int pos=0; ans=INF; for (long long i=0; i<pp.size()-1; i++){ ans=min(ans,pre[i]+suf[i+1]); } // cout << ans << ' ' << suf[pos] << "\n"; ans+=(luu.size()/2); ans+=sum2; cout << ans; } bool cmp(pair<long long, long long> a, pair<long long, long long> b) { return a.first + a.second < b.first + b.second; } 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}); } sort(all(pp),cmp); if (k==1) sub1(); else sub2(); }

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

bridge.cpp: In function 'void sub2()':
bridge.cpp:197:30: 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]
  197 |         for (long long i=0; i<pp.size(); i++){
      |                             ~^~~~~~~~~~
bridge.cpp:308:30: 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]
  308 |         for (long long i=0; i<pp.size()-1; i++){
      |                             ~^~~~~~~~~~~~
bridge.cpp:305:13: warning: unused variable 'pos' [-Wunused-variable]
  305 |         int pos=0;
      |             ^~~
#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...