제출 #412142

#제출 시각아이디문제언어결과실행 시간메모리
412142dolijanArranging Shoes (IOI19_shoes)C++14
50 / 100
271 ms283616 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; long long cnt=0; const int mn=1e5+100; vector<queue<int> > poz(mn); vector<queue<int> > neg(mn); set<int> skup; 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) { for(l;l<=r;l++) { if(l>=r) continue; int prva=s[l]; if(query(l,l,0,n-1,0)==1) continue; 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); //for(int i=0;i<n;i++) cout<<st[i]<<" "; //cout<<endl; } 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); } } } 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; }

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

shoes.cpp: In function 'void resi(int, int, int, std::vector<int>)':
shoes.cpp:31:9: warning: statement has no effect [-Wunused-value]
   31 |     for(l;l<=r;l++)
      |         ^
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:71:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     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...