| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 242224 | tqbfjotld | Jousting tournament (IOI12_tournament) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define inbuf_len 1 << 16
#define outbuf_len 1 << 16
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E);
int main() {
int tmp;
/* Set input and output buffering */
char *inbuf, *outbuf;
inbuf = (char*) malloc(inbuf_len * sizeof(char));
outbuf = (char*) malloc(outbuf_len * sizeof(char));
tmp = setvbuf(stdin, inbuf, _IOFBF, inbuf_len);
assert(tmp == 0);
tmp = setvbuf(stdout, outbuf, _IOFBF, outbuf_len);
assert(tmp == 0);
int N, C, R;
int *K, *S, *E;
tmp = scanf("%d %d %d", &N, &C, &R);
assert(tmp == 3);
K = (int*) malloc((N-1) * sizeof(int));
S = (int*) malloc(C * sizeof(int));
E = (int*) malloc(C * sizeof(int));
int i;
for (i = 0; i < N-1; i++) {
tmp = scanf("%d", &K[i]);
assert(tmp == 1);
}
for (i = 0; i < C; i++) {
tmp = scanf("%d %d", &S[i], &E[i]);
assert(tmp == 2);
}
printf("%d\n", GetBestPosition(N, C, R, K, S, E));
return 0;
}
/*
5 3 3
1 0 2 4
1 3
0 1
0 1
10 9 9
0 1 2 3 4 5 6 7 8
8 9
7 8
6 7
5 6
4 5
3 4
2 3
1 2
0 1
*/
#include <bits/stdc++.h>
using namespace std;
pair<int,int> actual[100005];
int fenwick[100005];
int qu(int p){
p++;
int ans = 0;
while (p>0){
ans += fenwick[p];
p-= (p&-p);
}
return ans;
}
void upd(int p, int v){
p++;
while (p<100005){
fenwick[p] += v;
p += (p&-p);
}
}
bool cmp(pair<int,int> a, pair<int,int> b){
if (a.first==b.first) return a.second>b.second;
return a.first<b.first;
}
vector<int> adjl[100005];
int ranks[100005];
int k;
struct nd{
int s,e,v;
nd *l,*r;
nd(int _s, int _e){
s = _s;
e = _e;
if (s==e){
v = ranks[s];
}
else{
l = new nd(s,(s+e)/2);
r = new nd((s+e)/2+1,e);
v = max(l->v,r->v);
//printf("v %d %d = %d\n",s,e,v);
}
}
int query(int a, int b){
if (a<=s && e<=b) return v;
if (b<=(s+e)/2) return l->query(a,b);
if (a>(s+e)/2) return r->query(a,b);
return max(l->query(a,b),r->query(a,b));
}
}*root;
pair<int,int> dfs(int node, int dist){
int mx = root->query(actual[node].first,actual[node].second-1);
//printf("querying %d %d\n",actual[node].first,actual[node].second-1);
//printf("node %d, mx %d\n",node,mx);
if (mx>k){
dist = 0;
}
int nd = -1;
pair<int,int> ans = {-1,-1};
int r = actual[node].first-1;
for (auto x : adjl[node]){
if (nd==-1 && actual[x].first>r+1){
nd = r+1;
}
auto res = dfs(x,dist+1);
if (res.first>ans.first || (res.first==ans.first && res.second<ans.second)){
ans = res;
}
}
if (nd==-1 && r<actual[node].second){
nd = r+1;
}
if (nd!=-1){
if (dist>ans.first || (ans.first==dist && nd<ans.second)){
ans = {dist,nd};
}
}
return ans;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
k = R;
for (int x = 0; x<N-1; x++){
ranks[x] = K[x];
//printf("ranks %d = %d\n",x,K[x]);
}
root = new nd(0,N-2);
//printf("%d\n",root->query(0,1));
for (int x = 0; x<C; x++){
actual[x] = {qu(S[x])+S[x],qu(E[x])+E[x]};
int offsetE = qu(E[x]);
upd(S[x],E[x]-S[x]+offsetE);
upd(E[x],offsetE+E[x]-S[x]-qu(E[x]));
assert(actual[x].second<N);
}
sort(actual,actual+C,cmp);
for (int x = 0; x<C; x++){
//printf("%d %d\n",actual[x].first,actual[x].second);
}
//return 0;
stack<int> st;
st.push(0);
for (int x = 1; x<C; x++){
if (actual[x].second<=actual[st.top()].second){
adjl[st.top()].push_back(x);
st.push(x);
}
else{
st.pop();
}
}
return dfs(0,R==N-1?1:0).second;
}