| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 235783 | FlowerOfSorrow | Arranging Shoes (IOI19_shoes) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
#include "ext/rope"
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
mt19937 rng(high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rngll(high_resolution_clock::now().time_since_epoch().count());
#define lambdify(x) [&](auto &&...args){ return x(forward<decltype(args)>(args)...); }
template<typename T, typename U> T &ctmax(T &x, const U &y){ return x = max<T>(x, y); }
template<typename T, typename U> T &ctmin(T &x, const U &y){ return x = min<T>(x, y); }
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
struct segment{
int n;
vector<int> val;
segment(int n): n(n), val(n << 1, 1){
for(auto i = n - 1; i > 0; -- i){
val[i] = val[i << 1] + val[i << 1 ^ 1];
}
}
void update(int p, int x){
for(val[p += n] += x; p > 1; p >>= 1){
val[p >> 1] = val[p] + val[p ^ 1];
}
}
int query(int l, int r){
int res = 0;
for(l += n, r += n; l < r; l >>= 1, r >>= 1){
if(l & 1){
res += val[l ++];
}
if(r & 1){
res += val[-- r];
}
}
return res;
}
};
long long count_swaps(vector<int> a){
int n = int(a.size()) / 2;
vector<vector<int>> pos(n);
long long res = 0;
for(auto i = 0; i < 2 * n; ++ i){
cin >> a[i];
if(int(pos[abs(a[i]) - 1].size()) % 2 && a[i] < 0){
++ res;
}
a[i] = abs(a[i]) - 1;
pos[a[i]].push_back(i);
}
segment tr(2 * n);
for(auto i = 2 * n - 1; i >= 0; -- i){
if(int(pos[a[i]].size()) % 2 == 0){
int p = *next(pos[a[i]].rbegin());
res += tr.query(p + 1, i);
tr.update(p, -1);
}
pos[a[i]].pop_back();
}
return res;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
return 0;
}
/*
*/
////////////////////////////////////////////////////////////////////////////////////////
// //
// Coded by Aeren //
// //
////////////////////////////////////////////////////////////////////////////////////////