Submission #151382

#TimeUsernameProblemLanguageResultExecution timeMemory
151382alexandra_udristoiuArranging Shoes (IOI19_shoes)C++14
0 / 100
2 ms376 KiB
#include "shoes.h" #include<iostream> #include<vector> #define DIM 200005 using namespace std; static int n; static int v[DIM], aib[DIM], st[DIM], dr[DIM], ff[DIM]; static void update(int x, int val){ for(; x <= n; x += (x & -x) ){ aib[x] += val; } } static int query(int x){ int sum = 0; for(; x >= 1; x -= (x & -x) ){ sum += aib[x]; } return sum; } long long count_swaps(vector<int> s) { int i; long long sol = 0; n = s.size(); for(i = 1; i <= n; i++){ v[i] = s[i - 1]; update(i, 1); } for(i = n; i >= 1; i--){ if(v[i] < 0){ ff[i] = dr[ -v[i] ]; dr[ -v[i] ] = 0; if(ff[i] == 0){ st[ -v[i] ] = i; } } else{ ff[i] = st[ v[i] ]; st[ v[i] ] = 0; if(ff[i] == 0){ dr[ v[i] ] = i; } } } for(i = 1; i <= n; i++){ if(ff[i] != 0){ sol += query(ff[i]) - query(i); update(ff[i], -1); } } return sol; }
#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...