제출 #288924

#제출 시각아이디문제언어결과실행 시간메모리
288924phillipArranging Shoes (IOI19_shoes)C++14
10 / 100
8 ms9728 KiB
#include "shoes.h" #include <bits/stdc++.h> #define ll long long #define fast cin.tie(0);cout.tie(0); #define order ios::sync_with_stdio(0);ios_base::sync_with_stdio(0); #define pb push_back #define ln 2*x+1 #define rn 2*x+2 #define m (l+r)/2 using namespace std; int n; vector<int>v[200009][2]; int cass(int x) { if(x>0)return 1; else return 0; } ll seg[1000009]; void bld(int x,int l,int r) { if(l==r) { seg[x]=1; return; } bld(ln,l,m); bld(rn,m+1,r); seg[x]=seg[ln]+seg[rn]; } void upd(int x,int l,int r,int w) { if(l==r) { seg[x]=0; return; } if(m<=w)upd(ln,l,m,w); else upd(rn,m+1,r,w); seg[x]=seg[ln]+seg[rn]; } ll qu(int x,int l,int r,int b,int e) { if(b>e)return 0; if(b<=l&&r<=e)return seg[x]; ll ret=0; if(m>=b)ret+=qu(ln,l,m,b,e); if(m<e)ret+=qu(rn,m+1,r,b,e); return ret; } int vis[200009]; long long count_swaps(vector<int> s) { n=s.size()/2; for(int i=n*2-1;i>=0;i--) { v[abs(s[i])][cass(s[i])].push_back(i); } bld(0,0,n*2-1); ll ans=0; for(int i=0;i<2*n;i++) { if(vis[i])continue; int x=s[i]; if(x<0)x*=-1; else ans++; int v1=v[x][0].back(),v2=v[x][1].back(); v[x][0].pop_back(); v[x][1].pop_back(); ans+=qu(0,0,n-1,min(v1,v2)+1,max(v1,v2)-1); upd(0,0,n-1,v1);upd(0,0,n-1,v2); vis[v1]=1; vis[v2]=1; } 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...