제출 #893059

#제출 시각아이디문제언어결과실행 시간메모리
893059Hugo1729Arranging Shoes (IOI19_shoes)C++17
100 / 100
232 ms275692 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; struct SegTree{ vector<int> e; int size; SegTree(int n){ size=1; while(size<n) size<<=1; e=vector<int>(2*size,0);}; void update(int v, int l, int r, int x, int y){ if (r<x||y<l) return; if (x<=l&&r<=y){ e[v]++; return;} int m=(l+r)/2; update(2*v,l,m,x,y); update(v*2+1,m+1,r,x,y); } int query(int v){ int ans=0; v+=size-1; while(v>0){ ans += e[v]; v/=2; } return ans; } }; long long count_swaps(std::vector<int> s) { int n= s.size(); long long ans =0; SegTree seg(n); deque<int> shoes[n+1][2]; for(int i=0;i<n;i++){ int shoe=s[i]; int j=(int)(shoe>0); shoe = abs(shoe); shoes[shoe][j].push_back(i+1); } for(int i=0;i<n;i++){ int shoe=s[i]; int j=(int)(shoe>0); shoe = abs(shoe); if (shoes[shoe][j].front() == i+1){ int pos = shoes[shoe][1-j].front(); shoes[shoe][1-j].pop_front(); shoes[shoe][j].pop_front(); ans+=(pos+seg.query(pos))-(i+1+seg.query(i+1))-1; ans+=j; seg.update(1,1,seg.size,i+1,pos); } } 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...