Submission #1215200

#TimeUsernameProblemLanguageResultExecution timeMemory
1215200ColourAttilaArranging Shoes (IOI19_shoes)C++17
100 / 100
261 ms104312 KiB
#include <bits/stdc++.h> // #include "shoes.h" #define ll long long #define pb push_back #define ff first #define ss second #define mp make_pair #define sz size() #define veg vegeta #define harderahhh ios::sync_with_stdio(0); cin.tie(0); cout.tie(0) const int N = 1e9+7; const int M = 998244353; using namespace std; ll x, l, y, t, z, hp, sus1, sus2, g, sus, sus3, bruh, bruh1, bruh2, bruh3, dog1, h, r, dog2, dog3; ll ck1, ck2, ck3, dog, i, p, j, q, m, a[1000005], b[696969], c[696969], n, k, d[2000005], e[696969]; ll x2[696969], x17[696969], x1[696969], joy[1005][1005], pp[1005][1005], di[1234566], de[1234566]; string s1, s2, s3, s4, s5, s6, s7, s8, s9, rep1, rep2, rep, s, hsr[696969], gi[696969]; char c1, c2, oon, hi[1005][1005], na[1005][1005], cc[696969], dd[696969]; pair <ll, ll> goku[696969], veg[696969]; vector<ll> aag[1000005], eeg[200005], ski, bidi; bool vis[200005]; map <pair<ll,ll>, ll> mm; map <ll, ll> wii, waa; set <ll> kk; void dfs(ll x) { } 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); } }; map <ll,vector<ll>> mma; ll count_swaps(vector<int>v){ vector<int>s; ll n = v.size()/2; s.pb(-1e9); for(auto x : v)s.pb(x); for (i = 1; i < s.sz; i++) { mma[s[i]].pb(i); } x=1; segtree diddy(2*n); sus=0; for (i = 1; i <= 100000; i++) { for (j = 0; j < mma[i].sz; j++) { if (mma[-i][j] < mma[i][j]) { goku[x].ff = mma[-i][j]+1; goku[x].ss = mma[i][j]-1; } else { goku[x].ff = mma[i][j]+1; goku[x].ss = mma[-i][j]-1; sus++; } x++; } } sort (goku+1, goku+x); for (i = 1; i < x; i++) { sus += diddy.query(1, 1, n*2, goku[i].ff, goku[i].ss); diddy.update(1, 1, n*2, goku[i].ss+1, 0); } return sus; }
#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...