제출 #987528

#제출 시각아이디문제언어결과실행 시간메모리
987528huutuan마상시합 토너먼트 (IOI12_tournament)C++14
0 / 100
73 ms10700 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template<class T> using ordered_set=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) { ordered_set<pair<int, int>> st; for (int i=0; i<N; ++i) st.insert({i, i}); vector<pair<int, int>> v; vector<vector<int>> vl(N), vr(N); for (int i=0; i<C; ++i){ int l=S[i], r=E[i]; auto it=st.find_by_order(l); int x=it->first, y=-1; int cnt=r-l+1; while (cnt--){ y=it->second; it=st.erase(it); } st.insert({x, y}); v.emplace_back(x, y); vl[x].push_back(y); vr[y].push_back(x); } int LG=32-__builtin_clz(N-1); vector<vector<int>> sp(LG, vector<int>(N-1)); for (int i=0; i<N-1; ++i) sp[0][i]=K[i]; for (int k=1; k<LG; ++k) for (int i=0; i+(1<<k)-1<N-1; ++i) sp[k][i]=max(sp[k-1][i], sp[k-1][i+(1<<(k-1))]); auto query=[&](int l, int r) -> int { int lg=__lg(r-l+1); return max(sp[lg][l], sp[lg][r-(1<<lg)+1]); }; int ans=0, cur=0; for (int i=0; i<N; ++i){ for (int j:vl[i]){ cur+=query(i, j-1)<R; } ans=max(ans, cur); for (int j:vr[i]){ cur-=query(j, i-1)<R; } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...