Submission #412102

#TimeUsernameProblemLanguageResultExecution timeMemory
412102dolijanArranging Shoes (IOI19_shoes)C++14
0 / 100
672 ms1048580 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; long long cnt=0; const int mn=1e6+100; vector<queue<int> > poz(mn); vector<queue<int> > neg(mn); set<int> skup; int ali[mn]; int st[4*mn]; void update(int l,int r,int poz,int tren) { if(l==r) { st[tren]++; return; } int mid=(l+r)/2; if(poz<=mid) update(l,mid,poz,2*tren+1); else update(mid+1,r,poz,2*tren+2); st[tren]=st[2*tren+1]+st[2*tren+2]; } int query(int l,int r,int L,int R,int node) { if(R<l || r<L) return 0; if(l<=L && R<=r) return st[node]; int mid=(L+R)/2; return query(l,r,L,mid,2*node+1)+query(l,r,mid+1,R,2*node+2); } void resi(int l,int r,int n,std::vector<int> s) { if(l>=r) return; int prva=s[l]; if(st[l]) goto kraj; if(prva>0) { poz[prva].pop(); int i=neg[prva].front(); neg[prva].pop(); //cout<<"Obradjujemo pozitivan "<<prva<<endl; //cout<<i<<endl; int manji=query(l+1,i,0,n-1,0); //cout<<"Kveri uradio "<<manji<<endl; cnt+=(i-l-manji); //cout<<cnt<<endl; update(0,n-1,i,0); } else { prva*=-1; neg[prva].pop(); int i=poz[prva].front(); //cout<<"Obradjujemo negativan "<<prva<<endl; //cout<<i<<endl; poz[prva].pop(); int manji=query(l+1,i,0,n-1,0); // cout<<"Uradio kveri ide gas "<<manji<<endl; cnt+=(i-(l+1)-manji); //cout<<cnt<<endl; update(0,n-1,i,0); } kraj: l+=1; resi(l,r,n,s); } long long count_swaps(std::vector<int> s) { int n=s.size(); int l=0; int r=n-1; for(int i=0;i<s.size();i++) { if(s[i]>0) poz[s[i]].push(i); else neg[-s[i]].push(i); } resi(l,r,n,s); return cnt; }

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:70:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     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...