제출 #185293

#제출 시각아이디문제언어결과실행 시간메모리
185293aggu_01000101Arranging Shoes (IOI19_shoes)C++14
0 / 100
2 ms376 KiB
#include <iostream> #include <vector> #include <shoes.h> #include <map> #include <unordered_map> #define int long long #define mid(l, u) ((l+u)/2) #define lchild(i) (i*2 + 1) #define rchild(i) (i*2 + 2) using namespace std; int query(int l, int u, int i, int ll, int uu, int segtree[], int lazy[]){ if(lazy[i]){ segtree[i]+=(u-l+1)*lazy[i]; if(l!=u){ lazy[lchild(i)]+=lazy[i]; lazy[rchild(i)]+=lazy[i]; } lazy[i] = 0; } if(l>=ll && u<=uu) return segtree[i]; if(l>uu || u<ll) return 0; return query(l, mid(l, u), lchild(i), ll, uu, segtree, lazy) + query(mid(l, u)+1, u, rchild(i), ll, uu, segtree, lazy); } int update(int l, int u, int i, int ll, int uu, int segtree[], int lazy[]){ if(ll>uu) return 0; if(lazy[i]){ segtree[i]+=(u-l+1)*lazy[i]; if(l!=u){ lazy[lchild(i)]+=lazy[i]; lazy[rchild(i)]+=lazy[i]; } lazy[i] = 0; } if(l>=ll && u<=uu){ segtree[i] += (u-l+1); if(l!=u){ lazy[lchild(i)]++; lazy[rchild(i)]++; } return segtree[i]; } if(l>uu || u<ll) return segtree[i]; return segtree[i] = update(l, mid(l, u), lchild(i), ll, uu, segtree, lazy) + update(mid(l, u)+1, u, rchild(i), ll, uu, segtree, lazy); } int count_swaps(vector<int32_t> s){ int n = s.size(); //cout<<n<<endl; int segtree[4*n], lazy[4*n]; for(int i = 0;i<4*n;i++) segtree[i] = lazy[i] = 0; unordered_map<int, vector<int>> mp; for(int i = n-1;i>=0;i--){ mp[s[i]].push_back(i); } int ans = 0; for(int i = 0;i<n;i++){ //cout<<i<<" "<<mp[-s[i]][mp[-s[i]].size()-1]<<endl; if(mp[-s[i]][mp[-s[i]].size()-1]>i) continue; int oind = mp[-s[i]][mp[-s[i]].size()-1]; int toadd; if(s[i]>0){ toadd = i - oind - 1; toadd-=query(0, n-1, 0, oind, oind, segtree, lazy); } else{ toadd = i - oind; toadd-=query(0, n-1, 0, oind, oind, segtree, lazy); } //cout<<i<<" "<<mp[-s[i]]<<" "<<toadd<<endl; ans+=toadd; update(0, n-1, 0, oind+1, i-1, segtree,lazy); mp[-s[i]].pop_back(); mp[s[i]].pop_back(); } cout<<ans<<endl; }

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

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:75:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
#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...