Submission #1215345

#TimeUsernameProblemLanguageResultExecution timeMemory
1215345brintonArranging Shoes (IOI19_shoes)C++20
10 / 100
0 ms328 KiB
#include <bits/stdc++.h> #include "shoes.h" using namespace std; struct BIT{ private: vector<int> tree; int N; void modify(int idx,int dv,int _){ for(int i = idx;i <= N;i+= i&-i){ tree[i] += dv; } } int query(int idx,int _){ int ans = 1; for(int i = idx;i >= 1;i-= i&-i){ ans += tree[i]; } return ans; } public: void modify(int idx,int dv){ modify(idx+1,dv,-1); } int query(int idx){ return query(idx+1,-1); } BIT(int iN){ N = iN; tree.resize(N+1); for(int i = 0;i < N;i++){ modify(i,1); } } }; long long count_swaps(vector<int> s) { int N = s.size()/2; vector<stack<int>> left(N+1); vector<stack<int>> right(N+1); long long ans = 0; BIT bit(2*N); for(int i = 0;i < 2*N;i++){ if(s[i] < 0){ // left if(!right[-s[i]].empty()){ // move right to left auto prev = right[-s[i]].top(); right[-s[i]].pop(); ans += bit.query(i)-bit.query(prev); bit.modify(prev,1); bit.modify(i,-1); }else{ left[-s[i]].push(i); } }else{ // right if(!left[s[i]].empty()){ // move left to right auto prev = left[s[i]].top(); left[s[i]].pop(); ans += bit.query(i)-bit.query(prev)-1; bit.modify(prev,1); bit.modify(i,-1); }else{ right[s[i]].push(i); } } } 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...