Submission #1048167

#TimeUsernameProblemLanguageResultExecution timeMemory
1048167nmtsPalembang Bridges (APIO15_bridge)C++17
100 / 100
58 ms9428 KiB
#include <bits/stdc++.h> #define file(name) freopen(name".inp" , " r " , stdin);freopen(name".out" , " w " , stdout); #define faster ios_base :: sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ; #define pii pair < int , int > #define fi first #define se second #define mii map< int , int> #define reset(a,val) memset(a ,val , sizeof(a) ) #define count_bit(i) __builtin_popcountll(i) #define mask(i) ((1LL << (i))) #define status(x, i) (((x) >> (i)) & 1) #define set_on(x, i) ((x) | mask(i)) #define set_off(x, i) ((x) & ~mask(i)) #define endl '\n' #define ll long long #define int ll const int maxn = 1e6 + 6; const int mod= 1e9 + 7; const ll INFLL= 3e18 + 5; const int INF = 1e9 + 5 ; const int LOG = 20 ; template <class T> inline T sqr(T x) { return x * x; }; template <class T> inline int Power(T x, int y) { if (!y) return 1; if (y & 1) return sqr(Power(x, y / 2)) % mod * x % mod; return sqr(Power(x, y / 2)) % mod; } template<class T> bool minimize(T& a, const T& b) { return b < a ? a = b, 1 : 0; } template<class T> bool maximize(T& a, const T& b) { return a < b ? a = b, 1 : 0; } inline int gcd(int x, int y) { return y ? gcd(y , x % y) : x;} inline int lcm(int x, int y) { return x * y / gcd(x, y); } using namespace std; int k , n; int dist = 0; vector<pii> path; // sub1 2 int calc(int x) { int res = 0; for (int i = 0 ; i < path.size() ; ++i) res += (abs(path[i].fi - x) + abs(path[i].se - x)); return res; } void solve1() { vector<int> a; for (int i = 0 ; i < path.size() ; ++i) a.push_back(path[i].fi) , a.push_back(path[i].se); sort(a.begin() ,a.end()); int k = (a.size() + 1) / 2 - 1; cout << dist + min(calc(a[k]) , min(calc(a[k - 1]) , calc(a[k + 1]))) << endl; // cout << a[k] << " " << calc(a[k]) << endl; } //---------------------------------------------------------------------------------------------- // sub 3 4 5 priority_queue<int , vector<int> , less<int>> low; priority_queue<int , vector<int> , greater<int>> up; int sum_low = 0; int sum_up = 0; int f[maxn]; void INSERT(int val) { int a = (low.empty() ? INF : low.top()); if (a < val) { up.push(val); sum_up += val; } else { low.push(val); sum_low += val; } if (up.size() + 1 < low.size()) { sum_low -= low.top(); sum_up += low.top(); up.push(low.top()); low.pop(); } if (low.size() < up.size()) { sum_up -= up.top(); sum_low += up.top(); low.push(up.top()); up.pop(); } } void solve2() { sort(path.begin() , path.end() , [&](pii a , pii b) { return a.fi + a.se < b.fi + b.se; }); sum_low = 0; sum_up = 0; for (int i = 0 ; i < path.size() ; ++i) { INSERT(path[i].fi); INSERT(path[i].se); f[i] = sum_up - sum_low; } sum_low = 0; sum_up = 0; while (up.size()) up.pop(); while (low.size()) low.pop(); int ans = f[path.size() - 1]; for (int i = path.size() - 1 ; i >= 0 ; --i) { INSERT(path[i].fi); INSERT(path[i].se); minimize(ans , sum_up - sum_low + f[i - 1]); } cout << ans + dist << endl; } void solve() { cin >> k >> n ; for (int i = 1 ; i <= n; ++i) { char a , b ; int x , y ; cin >> a >> x >> b >> y; if (a == b) dist += abs(x - y); else path.push_back({x , y}); } dist += path.size(); if (k == 1) solve1(); if (k == 2) solve2(); } int32_t main() { faster; // file("txt"); // int t ; cin >> t ; while (t--) solve(); return 0; }

Compilation message (stderr)

bridge.cpp: In function 'long long int calc(long long int)':
bridge.cpp:54:24: 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]
   54 |     for (int i = 0 ; i < path.size() ; ++i)
      |                      ~~^~~~~~~~~~~~~
bridge.cpp: In function 'void solve1()':
bridge.cpp:64:24: 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]
   64 |     for (int i = 0 ; i < path.size() ; ++i)
      |                      ~~^~~~~~~~~~~~~
bridge.cpp: In function 'void solve2()':
bridge.cpp:136:24: 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]
  136 |     for (int i = 0 ; i < path.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...