Submission #1193390

#TimeUsernameProblemLanguageResultExecution timeMemory
1193390yoshiArranging Shoes (IOI19_shoes)C++20
0 / 100
204 ms63656 KiB
#include<bits/stdc++.h> #define ll long long #define pb push_back #define ss second #define ff first using namespace std; ll df[1234567],ans; vector<ll> vv[1234567]; struct segtree{ ll n; vector<ll>d; segtree(ll n){ d.resize(4*n); build(1,1,n); } void build(ll v, ll l, ll r){ if(l == r){ d[v] = 1; return; } ll m = (l+r)/2; build(v*2,l,m); build(v*2+1,m+1,r); d[v] = d[v*2]+d[v*2+1]; } void update(ll v,ll l, ll r, ll pos, ll val){ if(pos < l or pos > r)return; if(l == r){ d[v] = val; return; } ll m = (l+r)/2; update(v*2,l,m,pos,val); update(v*2+1,m+1,r,pos,val); d[v] = d[v*2]+d[v*2+1]; } ll query(ll v, ll l, ll r, ll L, ll R){ if(R<L||R<l||r<L) return 0ll; if(L<=l&&r<=R) return d[v]; ll m = (l+r)/2; return query(v*2,l,m,L,R) + query(v*2+1,m+1,r,L,R); } }; int count_swaps(vector<int> a){ int n = a.size() / 2; vector<ll> s(1, 0); for(auto x : a) s.pb(x); map<ll, vector<ll>> w; for(ll i = 1; i < s.size(); i++){ w[s[i]].pb(i); } segtree seg(2 * n); vector<pair<ll, ll>> v; ll cnt = 0; for(ll i = 1; i <= 100000; i++){ if(w.find(i) == w.end() || w.find(-i) == w.end()) continue; if(w[i].size() != w[-i].size()) return -1; for(ll j = 0; j < w[i].size(); j++){ ll x = w[-i][j]; ll y = w[i][j]; if(x < y){ v.pb({x + 1, y - 1}); } else { v.pb({x - 1, y + 1}); cnt++; } } } sort(v.begin(), v.end()); for(auto [l, r] : v){ cnt += seg.query(1, 1, 2 * n, l, r); seg.update(1, 1, 2 * n, r + 1, 0); } return cnt; }
#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...