제출 #854642

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
854642		AliHasanli	Arranging Shoes (IOI19_shoes)	C++17	컴파일 에러	0 ms	0 KiB

shoes

#include<iostream> 
#include<vector>
#include<map>
#include<set>
using namespace std;
vector<int>sgtree(262144);
map<int,set<int>>mp;
int indd(int ind)
{
    int ans=131072+ind;
    return ans;
}
void update(int ind)
{
    if(ind==1){sgtree[ind]+=1;return;}
    sgtree[ind]+=1;
    update(ind/2);
}
int query(int L,int R,int l,int r,int index)
{
    if(l>r) return 0;
    if(r<L || R<l)return 0;
    if(l==r)return sgtree[index];
    if(L<=l && r<=R) return sgtree[index];
    return query(L,R,l,(l+r)/2,index*2)+query(L,R,(r+l)/2+1,r,index*2+1);
}
long long count_swaps(vector<int> s)
{
    long long ans=0;
    int a[s.size()]={0};
    for(int i=0;i<s.size();i++)
        sgtree[131072+i]=a[i];
    for(int i=0;i<s.size();i++)
        mp[s[i]].insert(i);
    for(int i=0;i<s.size();i++)
    {
        if(a[i]==0)
        {
        a[i]=1;
        mp[s[i]].erase(0);
        mp[-s[i]].erase(0);
        int nextind=0;
        update(indd(i));
        for(int j:mp[-s[i]])
        {
            nextind=j;
            break;
        }
        update(indd(nextind));
        a[nextind]=1;
        if(i+1==nextind)
            if(s[i]>s[nextind])ans++;
        if(i+1<nextind)
        {
            ans+=(nextind-i-1-query(i+2,nextind,1,131072,1));
            if(s[i]>s[nextind])ans++;
        }
        }
    }
    return ans;
}
//1 2 3 4 -1 -2 -3 -4 
//1 1 1 1  1  1  1  1
int main() 
{ 
    int n;
    cin>>n;
    vector<int>s(2*n);
    for(int i=0;i<2*n;i++)
        cin>>s[i];
    cout<<count_swaps(s);
    return 0; 
}// 1 -1 -1 1 


// 1:  1 4 
//-1:  2 3  

컴파일 시 표준 에러 (stderr) 메시지

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:31:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int i=0;i<s.size();i++)
      |                 ~^~~~~~~~~
shoes.cpp:33:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(int i=0;i<s.size();i++)
      |                 ~^~~~~~~~~
shoes.cpp:35:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i=0;i<s.size();i++)
      |                 ~^~~~~~~~~
/usr/bin/ld: /tmp/ccBoysXT.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc38Rz3S.o:shoes.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status