| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 842351 | nasir_bashirov | Arranging Shoes (IOI19_shoes) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
#define int long long
#define db long double
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define all(x) x.begin(), x.end()
#define fastio\
ios_base::sync_with_stdio(0);\
cin.tie(0);\
cout.tie(0)\
const int sz = 1e5 + 5;
int t[sz * 4], lazy[sz * 4], n;
map<int, deque<int>> mp;
void push(int x, int lx, int rx){
if(lx == rx or t[x] == 0) return;
t[x * 2] += lazy[x], t[x * 2 + 1] += lazy[x];
lazy[x * 2] += lazy[x], lazy[x * 2 + 1] += lazy[x];
lazy[x] = 0;
}
void build(int x, int lx, int rx){
if(lx == rx){
t[x] = lx;
return;
}
int mid = (lx + rx) / 2;
build(x * 2, lx, mid);
build(x * 2 + 1, mid + 1, rx);
t[x] = max(t[x * 2], t[x * 2 + 1]);
}
void update(int l, int r, int v, int x, int lx, int rx){
push(x, lx, rx);
if(lx >= l and rx <= r){
t[x] += v;
lazy[x] += v;
return;
}
if(lx > r or l > rx) return;
int mid = (lx + rx) / 2;
update(l, r, v, x * 2, lx, mid);
update(l, r, v, x * 2 + 1, mid + 1, rx);
t[x] = max(t[x * 2], t[x * 2 + 1]);
}
int query(int l, int r, int x, int lx, int rx){
push(x, lx, rx);
if(lx >= l and rx <= r) return t[x];
if(lx > r or l > rx) return 0;
int mid = (lx + rx) / 2;
return max(query(l, r, x * 2, lx, mid), query(l, r, x * 2 + 1, mid + 1, rx));
}
int ind(int x){
return query(x, x, 1, 1, n);
}
long long count_swaps(vi s) {
n = s.size();
vi used(n + 5, false);
build(1, 1, n);
long long res = 0;
for(int i = 0; i < n; i++){
int indd = -1;
if(!mp[-s[i]].empty()) indd = mp[-s[i]].front();
// cout << i << " " << indd << endl;
if(indd != -1){
res += ind(i + 1) - ind(indd + 1) - (s[i] > 0 ? 1 : 0);
// cout << "ind " << ind(i + 1) << " " << ind(indd + 1) << endl;
update(indd + 1, i, 1, 1, 1, n);
mp[-s[i]].pop_front();
}
else{
mp[s[i]].push_back(i);
}
}
return res;
}
// signed main() {
// int n;
// cin >> n;
// vector<int> v(2 * n);
// for(int i = 0; i < 2 * n; i++){
// cin >> v[i];
// }
// cout << "input ended" << endl;
// cout << count_swaps(v) << endl;
// }