제출 #424779

#제출 시각아이디문제언어결과실행 시간메모리
424779alireza_kavianiArranging Shoes (IOI19_shoes)C++14
100 / 100
97 ms14376 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; #define SZ(x) int((x).size()) #define all(x) (x).begin() , (x).end() #define sep ' ' const int MAXN = 2e5 + 10; int n , fen[MAXN] , mark[MAXN]; vector<int> pos[MAXN]; void add(int x , int v){ for(x++; x < MAXN ; x += x & -x) fen[x] += v; } int get(int x){ int ans = 0; for(x++ ; x > 0 ; x -= x & -x) ans += fen[x]; return ans; } ll count_swaps(vector<int> s) { n = SZ(s) / 2; ll ans = 0; for(int i = 0 ; i < n * 2 ; i++){ s[i] += n; add(i , 1); pos[s[i]].push_back(i); } for(int i = 0 ; i < MAXN ; i++) reverse(all(pos[i])); for(int i = 0 ; i < n * 2 ; i++){ if(mark[i]) continue; int x = i , y = pos[n + n - s[i]].back(); pos[s[i]].pop_back(); pos[n + n - s[i]].pop_back(); mark[x] = mark[y] = 1; // cout << x << sep << y << sep << get(x) << sep << get(y) << endl; ans += get(y) - get(x) - (s[x] < s[y]); add(x , 1); add(y , -1); } return ans; }
#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...