제출 #143267

#제출 시각아이디문제언어결과실행 시간메모리
143267tpoppoArranging Shoes (IOI19_shoes)C++14
100 / 100
229 ms141008 KiB
#include "shoes.h" #include<bits/stdc++.h> #define lsb(x) (x&(-x)) using namespace std; const int MAXN = 2e5 + 1000; const int OFFSET = 1e5 + 50; using pii = pair<int,int>; using ll = long long; struct fenwick{ int N; vector<ll> ft; void init(int n){ N=n; ft.resize(n+1); } void update(int pos,int delta){ for(++pos;pos<=N;pos+=lsb(pos)){ ft[pos]+=delta; } } ll query(int pos){ ll ans=0; for(++pos;pos!=0;pos-=lsb(pos)){ ans+=ft[pos]; } return ans; } ll sum(int a,int b){ return query(b)-query(a-1); } void debug(){ for(int i=0;i<N;i++){ cout<<i<<" "<<query(i)<<endl; } } }; deque<int> comb[MAXN]; fenwick ft; vector<pii> cp; int v[MAXN]; ll res = 0; long long count_swaps(std::vector<int> s) { for(int i=0;i<s.size();i++){ int val = s[i]; if(comb[val + OFFSET].empty()){ comb[OFFSET - val].push_back(i); }else{ if(s[i] < 0) cp.emplace_back(i,comb[val + OFFSET].front()); else cp.emplace_back(comb[val + OFFSET].front(),i); comb[val + OFFSET].pop_front(); } } sort(cp.begin(),cp.end(),[](pii a,pii b){ return a.first + a.second < b.first + b.second;}); for(int i=0;i<cp.size();i++){ v[2*i] = cp[i].first; v[2*i+1] = cp[i].second; } ft.init(2*cp.size()); for(int i=0;i<2*cp.size();i++){ //cout<<v[i]<< " " << s[v[i]] <<endl; res += i - ft.query(v[i]); ft.update(v[i],1); } return res; }

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

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:51:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<s.size();i++){
               ~^~~~~~~~~
shoes.cpp:64:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<cp.size();i++){
               ~^~~~~~~~~~
shoes.cpp:70:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<2*cp.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...