Submission #278486

#TimeUsernameProblemLanguageResultExecution timeMemory
278486ctziapoArranging Shoes (IOI19_shoes)C++14
50 / 100
208 ms44880 KiB
#include "shoes.h" #include <cstdio> #include <cassert> #include <iostream> #include <vector> using namespace std; int seg[500000]; void update(int s,int e,int u,int ind){ if(u<s || u>e){ return; } if(s==e && s==u){ seg[ind]=1; return; } 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]; } int query(int s,int e , int qs,int qe,int ind){ if(qs<=s && e<=qe){ return seg[ind]; } if(qs>e || qe<s){ return 0; } int mid=(s+e)/2; int p1=query(s,mid,qs,qe,ind*2); int p2=query(mid+1,e,qs,qe,ind*2+1); return p1+p2; } long long count_swaps(std::vector<int> s) { vector < int > row; vector < int > row2; vector < vector < int > > l(s.size()+1,row); vector < vector < int > > r(s.size()+1,row2); int li[s.size()+1]={}; int ri[s.size()+1]={}; for(int i=0;i<s.size();i++){ if(s[i]>0){ r[s[i]].push_back(i); } else l[-s[i]].push_back(i); } int ans=0; /// n log n int v[s.size()]={}; for(int i=0;i<s.size();i++){ int cou=0; if(v[i]==1){ continue; } int f=-s[i]; if(f>0){ li[f]++; int start=i; int e=r[f][ri[f]]; ri[f]++; 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]++; int start=i; int e=l[-f][li[-f]]; li[-f]++; 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; /* /// n^2 int v[s.size()]={}; for(int i=0;i<s.size();i++){ if(v[i]==1) continue; int cou=0; if(s[i]>0) cou=1; int f=-s[i]; for(int j=i+1;j<s.size();j++){ if(s[j]==f && v[j]!=1){ v[j]=1; v[i]=1; // cout<<cou<<" "<<i<<" "<<j<<endl; break; } if(v[j]==0){ cou++; } } ans+=cou; } */ }

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:55:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~
shoes.cpp:67:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for(int i=0;i<s.size();i++){
      |              ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...