제출 #523371

#제출 시각아이디문제언어결과실행 시간메모리
523371HappyPacManArranging Shoes (IOI19_shoes)C++14
50 / 100
129 ms49312 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 15; int BIT[MAXN]; void upd(int u){ u+=5; for(;u<MAXN;u+=u&(-u)) BIT[u]++; } int qry(int u){ u+=5; int rt = 0; for(;u>0;u-=u&(-u)) rt += BIT[u]; return rt; } long long count_swaps(std::vector<int> s) { map<int,vector<int> > mp; int N = s.size(); for(int i=N-1;i>=0;i--){ mp[s[i]].push_back(i); } long long res = 0; for(int i=0;i<N;i++){ if(qry(i)-qry(i-1) == 1) continue; int ref = mp[-s[i]].back(); mp[-s[i]].pop_back(); if(s[i] > 0) res += ref-qry(ref-1)+qry(i)-i; else res += ref-qry(ref-1)+qry(i)-i-1; mp[s[i]].pop_back(); upd(i); upd(ref); } 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...