| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 850022 | tosivanmak | 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;
#define ll long long
#define MIN -1e18
#define MAX 1e18
struct node{
ll maxi=0,mini=0,sum=0;
};
struct SEGtree{
vector<node>seg;
vector<ll>arr;
void init(ll n){
arr.resize(n+5);
seg.resize(4*n+5);
}
void build(ll l, ll r, ll id){
if(l==r){
seg[id].sum=arr[l];
seg[id].maxi=arr[l];
seg[id].mini=arr[l];
}
else{
ll mid=(l+r)>>1;
seg[id].sum=seg[id*2].sum+seg[id*2+1].sum;
seg[id].maxi=max(seg[id*2].maxi,seg[id*2+1].maxi);
seg[id].mini=min(seg[id*1].mini,seg[id*2+1].mini);
}
}
void upd(ll ul, ll l, ll r, ll id, ll val){
if(l==r){
seg[id].sum=val;
seg[id].maxi=val;
seg[id].mini=val;
}
else{
ll mid=(l+r)>>1;
if(ul<=mid){
upd(ul,l,mid,id*2,val);
}
else{
upd(ul,mid+1,r,id*2+1,val);
}
seg[id].sum=seg[id*2].sum+seg[id*2+1].sum;
seg[id].maxi=max(seg[id*2].maxi,seg[id*2+1].maxi);
seg[id].mini=min(seg[id*1].mini,seg[id*2+1].mini);
}
}
ll RMINQ(ll ql, ll qr, ll l, ll r, ll id){
if(l>qr||r<ql){
return MAX;
}
if(l>=ql&&r<=qr){
return seg[id].mini;
}
ll mid=(l+r)>>1;
return min(RMINQ(ql,qr,l,mid,id*2),RMINQ(ql,qr,mid+1,r,id*2+1));
}
ll RMAXQ(ll ql, ll qr, ll l, ll r, ll id){
if(ql>qr){
return MIN;
}
if(l>qr||r<ql){
return MIN;
}
if(l>=ql&&r<=qr){
return seg[id].maxi;
}
ll mid=(l+r)>>1;
return max(RMAXQ(ql,qr,l,mid,id*2),RMAXQ(ql,qr,mid+1,r,id*2+1));
}
ll RSUMQ(ll ql, ll qr, ll l, ll r, ll id){
if(l>qr||r<ql){
return 0;
}
if(l>=ql&&r<=qr){
return seg[id].sum;
}
ll mid=(l+r)>>1;
return RSUMQ(ql,qr,l,mid,id*2)+RSUMQ(ql,qr,mid+1,r,id*2+1);
}
}st;
struct pairs{
ll l,r;
bool operator<(const pairs& p)const{
// l,r,p.l,p.r
return r<p.r;
}
};
vector<pairs>bruh;
void merge(ll l, ll r, ll n){
ll mid=(l+r)>>1;
ll ptr=l,ptr2=mid+1;
vector<pairs>get;
for(int i=l;i<=r;i++){
if(ptr==mid+1){
get.push_back(bruh[ptr2]);
ptr2++;
}
else if(ptr2==r+1){
get.push_back(bruh[ptr]);
ptr++;
}
else if(bruh[ptr2]<bruh[ptr]&&bruh[ptr2].r<st.RMINQ(ptr,mid,0,n,1)){
get.push_back(bruh[ptr2]);
ptr2++;
}
else{
get.push_back(bruh[ptr]);
ptr++;
}
}
for(int i=l;i<=r;i++){
bruh[i]=get[i-l];
}
for(int i=l;i<=r;i++){
st.upd(i,0,n,1,bruh[i].r);
}
}
void merge_sort(ll l, ll r, ll n){
if(l==r){
st.upd(l,0,n,1,bruh[l].r);
return;
}
ll mid=(l+r)>>1;
merge_sort(l,mid,n);
merge_sort(mid+1,r,n);
merge(l,r,n);
}
struct FEN{
vector<ll>fen;
void init(ll n){
fen.resize(n+5);
for(int i=0;i<=n+4;i++){
fen[i]=0;
}
}
void upd(ll n, ll m, ll val){
for(int i=n;i<=m;i+=i&(-i)){
fen[i]+=val;
// cout<<i;
}
}
ll sum(ll e){
ll su=0;
while(e>=1){
su+=fen[e];
e-=e&(-e);
}
// cout<<1;
return su;
}
}f;
vector<int>adj[200005],adj2[200005]; int ptr[200005];
long long count_swaps(std::vector<int> s) {
vector<ll>make;
ll why=s.size();
st.init(why);
for(int i=0;i<why;i++){
if(s[i]<0){
make.push_back(-(s[i]));
adj[-(s[i])].push_back(i+1);
}
else{
adj2[s[i]].push_back(i+1);
}
}
for(int i=0;i<=why+4;i++){
ptr[i]=0;
}
// for(auto u: adj[2]){
// cout<<u<<" ";
// }
ll siz=make.size();
for(int i=0;i<siz;i++){
bruh.push_back({adj[make[i]][ptr[make[i]]],adj2[make[i]][ptr[make[i]]]});
ptr[make[i]]++;
}
// sort(bruh.begin(),bruh.end());
// for(int i=0;i<bruh.size();i++){
// for(int j=0;j<bruh.size()-1;j++){
// if(bruh[j+1]<bruh[j]){
// swap(bruh[j],bruh[j+1]);
// }
// }
// }
merge_sort(0,bruh.size()-1,bruh.size()-1);
vector<ll>real;
ll siz2=bruh.size();
for(int i=0;i<siz2;i++){
real.push_back(bruh[i].l);
real.push_back(bruh[i].r);
}
// for(auto u: real){
// cout<<u<<" ";
// }
f.init(200000);
ll ans=0;
ll siz3=real.size();
for(int i=0;i<siz3;i++){
ans+=f.sum(200000)-f.sum(real[i]);
// cout<<f.sum(200000)<<" "<<real[i]<<" ";
// cout<<f.sum(real[i])<<"\n";
f.upd(real[i],200000,1);
}
return ans;
// return 0;
}
// #ifndef ONLINE_JUDGE
int main() {
int n;
cin>>n;
vector<int> S(2 * n);
for (int i = 0; i < 2 * n; i++){
cin>>S[i];
}
long long result = count_swaps(S);
cout<<result<<"\n";
return 0;
}
// #endif