이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef pair<int, int> ii;
typedef tree<
ii, null_type, less<ii>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
const int M = 2e5 + 10;
struct node {
int sum, flag, l, d;
node(int s=0, int f=0, int l=0, int d=0) :
sum(s), flag(f), l(l), d(d) {}
} t[M];
int idx;
ordered_set st;
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
for(int i = 0; i < N - 1; i++) {
t[i] = node(K[i] > R, K[i] > R, i, 0);
st.insert({i, i});
}
t[N - 1] = node(0, 0, N - 1, 0);
st.insert({N - 1, N - 1});
idx = N;
for(int i = 0; i < C; i++) {
int l = S[i], r = E[i];
auto s = st.find_by_order(l);
auto e = st.find_by_order(r);
int lid = s -> second, rid = e -> second;
t[idx].l = t[lid].l;
// cout << "Processing " << S[i] << " " << E[i] << endl;
// cout << "lid " << lid << ", rid " << rid << endl;
vector<ordered_set::iterator> v;
while(1) {
int id = s -> second;
// cout << "merge node " << id << endl;
t[idx].sum += t[id].sum;
t[idx].d = max(t[idx].d, t[id].d + 1);
v.push_back(s);
if(s == e) break;
s++;
}
for(auto it : v) st.erase(it);
t[idx].flag = t[rid].flag;
st.insert({l, idx});
// cout << idx << " " << t[idx].l << " " << t[idx].sum << " " << t[idx].d << endl;
idx++;
}
int maxwin = 0, ans = 0;
for(int i = 0; i < idx; i++) if(t[i].d >= maxwin){
if(t[i].sum == 0 || (t[i].sum == 1 && t[i].flag)) {
if(t[i].d > maxwin) {
maxwin = t[i].d;
ans = t[i].l;
} else {
ans = min(ans, t[i].l);
}
}
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |