Submission #1085782

#TimeUsernameProblemLanguageResultExecution timeMemory
1085782steveonalexCoin Collecting (JOI19_ho_t4)C++17
100 / 100
38 ms7392 KiB
// #include "rect.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; #define MASK(i) (1LL << (i)) #define GETBIT(mask, i) (((mask) >> (i)) & 1) #define ALL(v) (v).begin(), (v).end() #define block_of_code if(true) ll max(ll a, ll b){return (a > b) ? a : b;} ll min(ll a, ll b){return (a < b) ? a : b;} ll gcd(ll a, ll b){return __gcd(a, b);} ll lcm(ll a, ll b){return a / gcd(a, b) * b;} ll LASTBIT(ll mask){return (mask) & (-mask);} int pop_cnt(ll mask){return __builtin_popcountll(mask);} int ctz(ull mask){return __builtin_ctzll(mask);} int logOf(ull mask){return 63 - __builtin_clzll(mask);} mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);} double rngesus_d(double l, double r){ double cur = rngesus(0, MASK(60) - 1); cur /= MASK(60) - 1; return l + cur * (r - l); } template <class T1, class T2> bool maximize(T1 &a, T2 b){ if (a < b) {a = b; return true;} return false; } template <class T1, class T2> bool minimize(T1 &a, T2 b){ if (a > b) {a = b; return true;} return false; } template <class T> void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){ for(auto item: container) out << item << separator; out << finish; } template <class T> void remove_dup(vector<T> &a){ sort(ALL(a)); a.resize(unique(ALL(a)) - a.begin()); } const ll INF = 1e18 + 69; int main(void){ ios::sync_with_stdio(0);cin.tie(0); cout.tie(0); clock_t start = clock(); int n; cin >> n; vector<pair<int, int>> point(n * 2); for(int i = 0; i<n*2; ++i) cin >> point[i].first >> point[i].second; ll ans = 0; for(pair<int, int> &i: point){ pair<int, int> cur = i; maximize(cur.first, 1); maximize(cur.second, 1); minimize(cur.first, n); minimize(cur.second, 2); ans += abs(i.first - cur.first) + abs(i.second - cur.second); i = cur; } int cnt[n][2]; memset(cnt, 0, sizeof cnt); for(pair<int, int> i: point) cnt[i.first-1][i.second-1]++; int k = 0; for(int i = 0; i<n; ++i){ k += cnt[i][0] + cnt[i][1]; ans += abs((i + 1) * 2 - k); } int leak[2]; memset(leak, 0, sizeof leak); for(int i = 0; i<n; ++i){ for(int j = 0; j <= 1; ++j) leak[j] += cnt[i][j]; while(leak[0] < i + 1 && leak[1] > i + 1){ leak[0]++; leak[1]--; ans++; } while(leak[1] < i + 1 && leak[0] > i + 1){ leak[1]++; leak[0]--; ans++; } } cout << ans << "\n"; cerr << "Time elapsed: " << clock() - start << " ms\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...