Submission #145535

#	Time	Username	Problem	Language	Result	Execution time	Memory
145535		Sarah_Mokhtar	Arranging Shoes (IOI19_shoes)	C++14	Compilation error	0 ms	0 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;
}
int main(){
    vector<int>s={2, 1, -1, -2};
    cout<<count_swaps(s);
}

Compilation message (stderr)

/tmp/ccgStaVn.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccXZdkld.o:shoes.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status