# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
876409 | Elvin_Fritl | Arranging Shoes (IOI19_shoes) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 545 , inf = 1e9 + 12 , mod = 1e9 + 7;
#include "shoes.h"
struct segtree {
int tree[N*3] , lazy[N*3] , mark[N*3];
void built(int v,int l,int r) {
if(l == r) {
tree[v] = 1;
return;
}
int mid = (l + r)/2;
built(v*2 , l , mid);
built(v*2 + 1 , mid+1 , r);
tree[v] = tree[v*2] + tree[v*2 + 1];
}
void push(int v,int l,int r) {
if(mark[v] == 0) {
return;
}
mark[v] = 0;
int mid = (l+r)/2;
lazy[v*2] = lazy[v*2 + 1] = lazy[v];
mark[v*2] = 1;
mark[v*2 + 1] = 1;
tree[v*2] += (mid - l + 1)*lazy[v*2];
tree[v*2] += (r - mid)*lazy[v*2 + 1];
}
void update(int v,int l,int r,int ml,int val) {
if(r < ml) {
return;
}
push(v , l , r);
if(ml <= l) {
mark[v] = 1;
lazy[v] += val;
tree[v] += val * (r - l + 1);
return;
}
int mid = (l + r)/2;
update(v , l , mid , ml , val);
update(v , mid + 1 , r , ml , val);
tree[v] = tree[v*2] + tree[v*2 + 1];
}
int get(int v,int l,int r,int ml) {
if(r < ml) {
return 0;
}
push(v , l , r);
if(ml <= l) {
return tree[v];
}
int mid = (l + r)/2;
return (get(v , l , mid , ml) + get(v , mid + 1 , r , ml));
}
};
segtree S;
int count_swaps(vector<int> v) {
int n = v.size();
set<pair<int , int>> s;
v.push_back(0);
for(int i = 2*n;i>=1;i--){
v[i] = v[i-1];
s.insert({v[i] , i});
}
S.built(1,1,2*n);
int res = 0;
for(int i=1;i<=2*n;i++) {
if(s.find({v[i] , i}) != s.end()){
if(v[i] > 0) {
res++;
}
auto it = s.upper_bound({-v[i] - 1 , i});
if((*it).second - 2 >= i) {
res += S.get(1,1,2*n,i + 1);
}
S.update(1 , 1 , 2*n , i, -1);
S.update(1 , 1 , 2*n , (*it).second, -1);
s.erase(s.find({v[i], i}));
s.erase(s.find({-v[i], (*it).second}));
}
}
return res;
}