제출 #145536

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
145536		Sarah_Mokhtar	Arranging Shoes (IOI19_shoes)	C++14	25 / 100	643 ms	27340 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10,M=(N<<4),OO=0x3f3f3f;
int pos[N],tree[M];
void build(int node,int l,int r){
    if(l==r) tree[node]=pos[l];
    else{
        int med=(l+r)/2;
        build(node<<1,l,med);
        build(node<<1|1,med+1,r);
        tree[node]=tree[node<<1]+tree[node<<1|1];
    }
}
void update(int node,int l,int r,int idx,int val){
    if(l>r || l>idx || r<idx)	return;
    if(l==r) tree[node]+=val;
    else{
        int med=(l+r)/2;
        update(node<<1,l,med,idx,val);
        update(node<<1|1,med+1,r,idx,val);
        tree[node]=tree[node<<1]+tree[node<<1|1];
    }
}
int query(int node,int s,int e,int l,int r){
    if(s>e||s>r||e<l) return 0;
    if(s>=l&&e<=r) return tree[node];
    int med=(s+e)/2;
    int q1=query(2*node,s,med,l,r);
    int q2=query(2*node+1,med+1,e,l,r);
    return max(q1,q2);
}
ll count_swaps(vector<int>s){
    map<int,vector<int>>m;
    ll ret=0;
    int n=s.size();
    for(int i=0;i<n;++i)
        update(1,0,n-1,i,1);
    for(int i=n-1;i>=0;--i)
        m[s[i]].push_back(i);
    for(int i=0;i<n;++i){
        if(query(1,0,n-1,0,i)-query(1,0,n-1,0,i-1)!=1) continue;
        int k=m[-s[i]].back();
        m[s[i]].pop_back();
        m[-s[i]].pop_back();
        update(1,0,n-1,i,-1);
        update(1,0,n-1,k,-1);
        ret+=query(1,0,n-1,0,k)-query(1,0,n-1,0,i);
        if(s[i]>0) ++ret;

    }
    return ret;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 15 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15