제출 #143551

#제출 시각아이디문제언어결과실행 시간메모리
143551muradeynArranging Shoes (IOI19_shoes)C++14
10 / 100
2 ms380 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; const int maxx = 100001; int fen[maxx]; void update(int idx) { idx++; while (idx < maxx)fen[idx]++ , idx += (idx & -idx); } int get(int idx) { idx++; int ret = 0; while (idx > 0) { ret += fen[idx]; idx -= (idx & -idx); } return ret; } int query(int l , int r) { l++; r++; if (l > r)return 0; return get(r) - get(l - 1); } map< int , queue<int> >mp; long long count_swaps(vector<int> s) { long long ret = 0; int n = s.size(); for (int i = 0;i<n;i++)mp[s[i]].push(i); for (int i = 0;i<n;i++) { if (mp[s[i]].front() == i) { int nxt = mp[-s[i]].front(); mp[s[i]].pop(); mp[-s[i]].pop(); ret += (nxt - i - 1) - query(i + 1 , nxt - 1); update(nxt); if (s[i] >= 0)ret++; } } return ret; }
#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...