Submission #703204

#TimeUsernameProblemLanguageResultExecution timeMemory
703204Doncho_BonbonchoArranging Shoes (IOI19_shoes)C++14
10 / 100
29 ms5428 KiB
#include <bits/stdc++.h> #include "shoes.h" typedef long long ll; const int MAX_N = 1e6 + 42; int p[MAX_N]; int last[MAX_N]; int tree[MAX_N]; void add( int x, int v ){ // std::cerr<<" ! "<<x<<"\n"; while( x < MAX_N ){ tree[x] += v; x += x&(-x); } } int query( int x ){ int nas = 0; while( x ){ nas += tree[x]; x -= x&(-x); } return nas; } bool oke[MAX_N]; bool l[MAX_N]; long long count_swaps(std::vector<int> s) { ll nas = 0; int n = s.size(); for( int i=1 ; i<=n ; i++ ){ if( s[i-1] < 0 ) l[i] = true; int curr = abs( s[i-1] ); // std::cerr<<" ! "<<curr<<"\n"; // std::cerr<<last[curr]<<"\n"; if( last[curr] == 0 ) last[curr] = i; else{ p[i] = last[curr]; p[last[curr]] = i; last[curr] = 0; } add( i, 1 ); } /* for( int i=1 ; i<=n ; i++ ) std::cerr<<p[i]<<" "; std::cerr<<"\n"; */ for( int i=1 ; i<=n ; i++ ){ while( i<=n and oke[i] ) i++; if( i > n ) break; ll currNas = query( p[i] )-1; if( l[i] ){ // std::cerr<<"l -> -1 \n"; currNas --; } // std::cerr<<" ! "<<i<<" "<<p[i]<<" -> "<<currNas<<"\n\n"; nas += currNas; add( i, -1 ); add( p[i], -1 ); oke[i] = true; oke[p[i]] = true; } return nas; }
#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...