Submission #1226386

#TimeUsernameProblemLanguageResultExecution timeMemory
1226386alexaaaArranging Shoes (IOI19_shoes)C++20
100 / 100
221 ms27032 KiB
#include<iostream> #include<vector> #include<map> #include<queue> #include<climits> using namespace std; vector<int> st(600000,0); void add(int index, int r_begin, int r_end, int x){ if(r_begin == r_end && r_begin == x){ st[index] ++; return; } int mid = (r_begin+r_end)/2; if(x <= mid){ add(index*2+1, r_begin, mid, x); } else { add(index*2+2,mid+1,r_end,x); } st[index]=st[index*2+1]+st[index*2+2]; return; } int query(int index, int r_begin, int r_end, int l, int r){ if(r_end < l || r_begin > r){ return 0; } if(r_begin >= l && r_end <= r){ return st[index]; } int mid = (r_begin + r_end)/2; return query(index*2+1,r_begin,mid,l,r) + query(index*2+2,mid+1,r_end,l,r); } long long count_swaps(vector<int> S){ int n = S.size(); vector<int> seen(n,0); map<int, priority_queue<int, vector<int>, greater<int>>> positive, negative; for(int i = 0; i < n; i++){ if(S[i] < 0){ negative[abs(S[i])].push(i); } else{ positive[S[i]].push(i); } } long long res = 0; int pos; for(int j = 0; j < n; j ++){ if(!seen[j]){ if(S[j] > 0){ pos = negative[S[j]].top(); } else{ pos = positive[abs(S[j])].top(); } negative[abs(S[j])].pop(); positive[abs(S[j])].pop(); res += abs(j - pos)-1; res -= query(0,0,n-1,j+1,pos); if(S[j]>0){ res ++; } seen[pos]=1; add(0,0,n-1,pos); } } return res; }
#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...