Submission #878852

#TimeUsernameProblemLanguageResultExecution timeMemory
878852niterCoin Collecting (JOI19_ho_t4)C++17
0 / 100
0 ms348 KiB
#include <bits/stdc++.h> #define pb push_back #define ins isnert #define pii pair<int,int> #define ff first #define ss second #define loop(i,a,b) for(int i = (a); i < (b); i ++) #define op(x) cerr << #x << " = " << x << endl; #define opa(x) cerr << #x << " = " << x << ", "; #define ops(x) cerr << x; #define spac cerr << ' '; #define entr cerr << endl; #define STL(x) cerr << #x << " : "; for(auto &qwe:x) cerr << qwe << ' '; cerr << endl; #define ARR(x, nnn) cerr << #x << " : "; loop(qwe,0,nnn) cerr << x[qwe] << ' '; cerr << endl; #define BAE(x) (x).begin(), (x).end() #pragma GCC optimize("O3") using namespace std; typedef long long ll; mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count()); vector<pii> v; //ostream& operator<<(ostream &os, pair<int, char> x){ // os << "[" << x.ff << ", " << x.ss << "]"; //} int main(){ ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n; m = n << 1; loop(i,0,m){ int x, y; cin >> x >> y; v.pb({x, y}); } long long ans = 0; // process X axis first vector<pair<int, char>> now; queue<int> S, T; for(auto &i:v){ now.pb({i.ff, 'S'}); } loop(i,1,n+1){ now.pb({i, 'T'}); now.pb({i, 'T'}); } sort(BAE(now)); // STL(now) for(auto &i:now){ if(i.ss == 'S'){ if(T.empty()) S.push(i.ff); else{ ans += i.ff - T.front(); T.pop(); } } else{ if(S.empty()) T.push(i.ff); else{ ans += i.ff - S.front(); S.pop(); } } } // then process Y axis now.clear(); for(auto &i:v){ now.pb({i.ss, 'S'}); } loop(i,1,n+1){ now.pb({1, 'T'}); now.pb({2, 'T'}); } sort(BAE(now)); // STL(now) assert(S.size() == 0); assert(T.size() == 0); for(auto &i:now){ if(i.ss == 'S'){ if(T.empty()) S.push(i.ff); else{ ans += i.ff - T.front(); T.pop(); } } else{ if(S.empty()) T.push(i.ff); else{ ans += i.ff - S.front(); S.pop(); } } } cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...