| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 144316 | CodeKracker | Arranging Shoes (IOI19_shoes) | C++14 | 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.
/*input
*/
/**
Author: Kristopher Paul
Date Created: 16-08-2019
Contest Name:
_/ _/ _/_/_/_/ _/ _/_/_/_/
_/ _/ _/ _/ _/ _/
_/_/ _/_/_/_/ _/ _/_/_/_/
_/ _/ _/ _/ _/ _/
_/ _/ _/ _/ _/ _/_/_/_/
**/
#include<bits/stdc++.h>
#define ll long long
#define int ll
#define pb push_back
#define INF 0x3f3f3f3f //0x3f3f3f3f = 63
#define MOD 1000000007
#define mp make_pair
const double PI=3.141592653589793238462643383279502884197169399375105820974944;
#define REP(i,n) for (int i = 0; i < n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REPD(i,n) for (int i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (int i = a; i >= b; i--)
#define remax(a,b) a = max(a,b)
#define remin(a,b) a = min(a,b)
#define umap unordered_map
#define pii pair<int,int>
#define F first
#define S second
#define mii map<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define itr :: iterator it
#define all(v) v.begin(),v.end()
#define WL(t) while(t--)
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) ((a)*(b))/gcd((a),(b))
#define out(x) cout << #x << " is " << x << endl
#define FastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
int ModExp(int x,int y,int m){
int res = 1;
x = x % m;
while (y > 0)
{
if (y & 1)
res = (res*x) % m;
y = y>>1;
x = (x*x) % m;
}
return res;
}
struct segnode
{
int lazy;
int val;
};
segnode tree[400005];
void build(int node,int s,int e){
if(s == e){
tree[node].lazy = 0;
tree[node].val = 0;
return;
}
int m = (s+e)/2;
build(node*2,s,m);
build(node*2+1,m+1,e);
tree[node].lazy = 0;
tree[node].val = tree[node*2].val + tree[node*2+1].val;
}
void upd(int node,int s,int e,int l,int r,int v){
if(tree[node].lazy != 0){
tree[node].val += (tree[node].lazy*(e-s+1));
if(s != e){
tree[node*2].lazy += tree[node].lazy;
tree[node*2+1].lazy += tree[node].lazy;
}
tree[node].lazy = 0;
}
if(s > r || e < l || s > e || l > r){
return;
}
if(l <= s && e <= r){
tree[node].val += (v*(e-s+1));
if(s != e){
tree[node*2].lazy += v;
tree[node*2+1].lazy += v;
}
return;
}
int m = (s+e)/2;
upd(node*2,s,m,l,r,v);
upd(node*2+1,m+1,e,l,r,v);
tree[node].val = tree[node*2].val + tree[node*2+1].val;
}
int query(int node,int s,int e,int pos){
if(tree[node].lazy != 0){
tree[node].val += (tree[node].lazy*(e-s+1));
if(s != e){
tree[node*2].lazy += tree[node].lazy;
tree[node*2+1].lazy += tree[node].lazy;
}
tree[node].lazy = 0;
}
if(s > pos || e < pos || s > e){
return 0;
}
if(s <= pos && pos <= e){
return tree[node].val;
}
int m = (s+e)/2;
int a = query(node*2,s,m,pos);
int b = query(node*2+1,m+1,e,pos);
tree[node].val = tree[node*2].val + tree[node*2+1].val;
return max(a,b);
}
int count_swaps(vector<int> arr){
int n = arr.size();
build(1,1,n);
umap<int,vi> op;
FORD(i,n-1,0){
op[arr[i]].pb(i+1);
}
int ans = 0;
FOR(i,0,n){
if(arr[i] < 0){
if(arr[i+1] == abs(arr[i])){
op[arr[i]].pop_back();
continue;
}
vi::iterator k = op[abs(arr[i])].end();
k--;
int pos = *k;
int rpos = query(1,1,n,pos) + pos;
int lpos = i+1;
ans += rpos-lpos-1;
upd(1,1,n,lpos+1,rpos-1,1);
upd(1,1,n,rpos,rpos,rpos-lpos-1);
}else if((arr[i] > 0 && -arr[i-1] != arr[i]) || (i == 0 && arr[i] > 0)){
vi::iterator k = op[-arr[i]].end();
k--;
int pos = *k;
int rpos = i+1;
int lpos = query(1,1,n,pos) + pos;
ans += lpos-rpos;
upd(1,1,n,rpos,lpos-1,1);
upd(1,1,n,lpos,lpos,lpos-rpos);
}else{
op[arr[i]].pop_back();
}
}
return ans;
}