제출 #201484

#제출 시각아이디문제언어결과실행 시간메모리
201484combi1k1Arranging Shoes (IOI19_shoes)C++14
100 / 100
304 ms274492 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define ld double #define sz(x) (int)x.size() #define all(x) x.begin(),x.end() #define pb emplace_back #define X first #define Y second const int N = 2e5 + 5; typedef pair<int,int> ii; int t[N]; int v[N]; int upd(int p,int v) { for(; p < N ; p += p & -p) t[p] += v; return 1; } int get(int p) { int ans = 0; for(; p > 0 ; p -= p & -p) ans += t[p]; return ans; } queue<int> lef[N]; queue<int> rig[N]; ll count_swaps(vector<int> S) { int n = S.size(); for(int i = 1 ; i <= n ; ++i) { int x = S[i - 1]; if (x < 0) lef[-x].push(i); if (x > 0) rig[ x].push(i); } for(int i = 1 ; i <= n ; ++i) upd(i,1); ld ans = 0; for(int i = 1 ; i <= n ; ++i) if(!v[i]) { int x = abs(S[i - 1]); int L = lef[x].front(); lef[x].pop(); int R = rig[x].front(); rig[x].pop(); if (L > R) { ans++; swap(L,R); } ans += get(R); ans -= get(L) + 1; upd(R,-1); v[R] = 1; } return ans; } //int main() { // ios_base::sync_with_stdio(0); // cin.tie(0); cout.tie(0); // // cout << count_swaps({-1,-2,-3,-4,-5,1,2,3,4,5}); //}
#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...