제출 #620443

#제출 시각아이디문제언어결과실행 시간메모리
620443cheissmartArranging Shoes (IOI19_shoes)C++14
100 / 100
93 ms16676 KiB
#include "shoes.h" #include <bits/stdc++.h> #define IO_OP ios::sync_with_stdio(0), cin.tie(0) #define F first #define S second #define V vector #define PB push_back #define EB emplace_back #define MP make_pair #define SZ(v) int((v).size()) #define ALL(v) (v).begin(), (v).end() using namespace std; typedef long long ll; typedef pair<int, int> pi; typedef V<int> vi; const int INF = 1e9 + 7, N = 2e5 + 7; int bit[N]; void add(int pos, int val) { for(; pos < N; pos += pos & -pos) bit[pos] += val; } int qry(int pos) { int res = 0; for(; pos; pos -= pos & -pos) res += bit[pos]; return res; } ll count_swaps(vi s) { int n = SZ(s) / 2; V<vi> posl(n); V<vi> posr(n); for(int i = 0; i < n * 2; i++) { if(s[i] < 0) { posl[-s[i] - 1].PB(i); } else { posr[s[i] - 1].PB(i); } } ll ans = 0; V<pi> aux; for(int i = 0; i < n; i++) { assert(SZ(posl[i]) == SZ(posr[i])); for(int j = 0; j < SZ(posl[i]); j++) { if(posl[i][j] > posr[i][j]) { ans++; swap(posl[i][j], posr[i][j]); } aux.EB(posl[i][j], posr[i][j]); } } sort(ALL(aux)); assert(SZ(aux) == n); vi p(2 * n); for(int i = 0; i < n; i++) { p[aux[i].F] = i * 2 + 1; p[aux[i].S] = i * 2 + 2; } for(int i = 2 * n - 1; i >= 0; i--) { ans += qry(p[i]); add(p[i], 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...