Submission #278497

#	Time	Username	Problem	Language	Result	Execution time	Memory
278497		ctziapo	Arranging Shoes (IOI19_shoes)	C++14	Compilation error	0 ms	0 KiB

shoes

#include "shoes.h"
#include <cstdio>
#include <cassert>
#include <iostream>
#include <vector>

using namespace std;

long long int seg[500000];

void update(long long int s,long long int e,long long int u,long long int ind){

   if(u<s || u>e){
    return;
   }

   if(s==e && s==u){
        seg[ind]=1;
        return;
   }

   long long int mid=(s+e)/2;
   update(s,mid,u,ind*2);
   update(mid+1,e,u,ind*2+1);

   seg[ind]=seg[ind*2]+seg[ind*2+1];
}

long long int query(long long int s,long long int e , long long int qs,long long int qe,long long int ind){

    if(qs<=s && e<=qe){
        return seg[ind];
    }
    if(qs>e || qe<s){
        return 0;
    }

   long long int mid=(s+e)/2;
   long long int p1=query(s,mid,qs,qe,ind*2);
   long long int p2=query(mid+1,e,qs,qe,ind*2+1);

   return p1+p2;

}
long long count_swaps(std::vector<long long int> s) {

    vector < long long int > row;
    vector < long long int > row2;
    vector < vector < long long int > > l(200000,row);
    vector < vector < long long int > > r(200000,row2);

    long long int li[200000+1]={};
    long long int ri[200000+1]={};

    for(long long int i=0;i<s.size();i++){
        if(s[i]>0){
            r[s[i]].push_back(i);
        }
        else
            l[-s[i]].push_back(i);
    }

	long long int ans=0;

	/// n log n
    long long int v[200000]={};
	for(long long int i=0;i<s.size();i++){
        long long int cou=0;
        if(v[i]==1){
            continue;
        }

        long long int f=-s[i];
        if(f>0){
        li[f]++;
        long long int start=i;
        long long int e=r[f][ri[f]];
        ri[f]++;
        long long int q=query(1,s.size(),start+1,e+1,1);

        v[start]=1;
        v[e]=1;

        update(1,s.size(),start+1,1);
        update(1,s.size(),e+1,1);
       // cout<<q<<endl;
        cou=cou + e-start-1-q;
        }
        else{
            cou=1;
             ri[-f]++;
             long long int start=i;
             long long int e=l[-f][li[-f]];
             li[-f]++;

            long long int q=query(1,s.size(),start+1,e+1,1);

             v[start]=1;
        v[e]=1;

        update(1,s.size(),start+1,1);
        update(1,s.size(),e+1,1);
         //   cout<<q<<endl;
             cou=cou + e-start-1-q;
        }
        ans+=cou;
	}

	return ans;


}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<long long int>)':
shoes.cpp:55:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(long long int i=0;i<s.size();i++){
      |                           ~^~~~~~~~~
shoes.cpp:67:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for(long long int i=0;i<s.size();i++){
      |                        ~^~~~~~~~~
/tmp/cc7hduGu.o: In function `main':
grader.cpp:(.text.startup+0x26a): undefined reference to `count_swaps(std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status