Submission #257697

#TimeUsernameProblemLanguageResultExecution timeMemory
257697HeheheArranging Shoes (IOI19_shoes)C++14
100 / 100
623 ms34284 KiB
#include<bits/stdc++.h> //:3 using namespace std; typedef long long ll; #define all(a) (a).begin(), (a).end() #define ff first #define ss second #define pb push_back #define mp make_pair #define pi pair<int, int> #define sz(x) (int)((x).size()) const int dx[] = {0, 1, 0, -1}; const int dy[] = {1, 0, -1, 0}; const int N = 1e6 + 11; map<int, set<int>>M; int t[N]; void update(int v, int l, int r, int pos, int val){ if(l == r){ t[v] = val; return; } int mid = (l + r) >> 1; if(pos <= mid)update(2*v, l, mid, pos, val);else update(2*v + 1, mid + 1, r, pos, val); t[v] = t[2*v] + t[2*v + 1]; } ll q(int v, int tl, int tr, int l, int r){ if(tl > r || tr < l)return 0; if(l <= tl && tr <= r){ return t[v]; } int mid = (tl + tr) >> 1; return q(2*v, tl, mid, l, r) + q(2*v + 1, mid + 1, tr, l, r); } ll count_swaps(vector<int> A){ int n = sz(A); vector<int>a; a.push_back(0); for(auto it : A)a.push_back(it); for(int i = 1; i <= n; i++){ update(1, 1, n, i, 1); M[a[i]].insert(i); } ll ans = 0; for(int i = 1; i <= n; i++){ if(q(1, 1, n, i, i) == 0)continue; if(a[i] > 0)ans++; int x = *M[-a[i]].begin(); ans += (i + 1 <= x - 1 ? q(1, 1, n, i + 1, x - 1) : 0); M[a[i]].erase(*M[a[i]].begin()); M[-a[i]].erase(*M[-a[i]].begin()); update(1, 1, n, i, 0); update(1, 1, n, x, 0); } return ans; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...