제출 #602985

#제출 시각아이디문제언어결과실행 시간메모리
602985definitelynotmeeArranging Shoes (IOI19_shoes)C++17
100 / 100
74 ms20372 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int,int>; using pll = pair<ll,ll>; template<typename T> using matrix = vector<vector<T>>; #define ff first #define ss second #define all(x) x.begin(), x.end() template<typename T> struct smartvec{ vector<T> v; int n; smartvec(int sz = 0){ n = sz; v = vector<T>(2*sz+1); } T& operator[](int id){ return v[id+n]; } }; long long count_swaps(std::vector<int> v) { int n = v.size(); ll resp = 0; vector<int> bit(n+1); auto update=[&](int id, int val){ id++; while(id<=n){ bit[id]+=val; id+=id&-id; } }; auto query =[&](int id){ id++; int ret = 0; while(id){ ret+=bit[id]; id-=id&-id; } return ret; }; smartvec<vector<int>> ocur(n); for(int i = n-1; i >= 0; i--){ update(i,1); ocur[v[i]].push_back(i); } vector<int> passed(n); for(int i = 0; i < n; i++){ if(passed[i]) continue; ocur[v[i]].pop_back(); update(i,-1); int next = ocur[v[i]*-1].back(); ocur[v[i]*-1].pop_back(); update(next,-1); passed[i] = 1; passed[next] = 1; resp+=query(next); resp+=v[i]> 0; } return resp; }
#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...