| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 575487 | ogibogi2004 | Jousting tournament (IOI12_tournament) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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);
//#include<bits/stdc++.h>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1e5+6;
const int lg=18;
int par[MAXN][lg];
vector<int>g[MAXN];
bool not_leaf[MAXN];
struct BIT
{
int fen[MAXN];
void update(int idx,int val)
{
idx++;
for(;idx<MAXN;idx+=idx&(-idx))
{
fen[idx]+=val;
}
}
int get_position(int idx)
{
idx++;
int ret=0;
for(;idx>0;idx-=idx&(-idx))
{
ret+=fen[idx];
}
return ret;
}
}real_positions1,real_positions2;
struct segment_tree
{
int tree[4*MAXN];
void build(int l,int r,int idx)
{
tree[idx]=MAXN;
if(l!=r)
{
int mid=(l+r)/2;
build(l,mid,idx*2);
build(mid+1,r,idx*2+1);
}
}
void update(int l,int r,int idx,int ql,int qr,int val)
{
if(l>qr)return;
if(r<ql)return;
if(l>=ql&&r<=qr)
{
tree[idx]=min(tree[idx],val);
return;
}
int mid=(l+r)/2;
update(l,mid,idx*2,ql,qr,val);
update(mid+1,r,idx*2+1,ql,qr,val);
}
int query(int l,int r,int idx,int q)
{
//cout<<l<<" "<<r<<" "<<idx<<" "<<q<<endl;
if(l>q)return MAXN;
if(r<q)return MAXN;
if(l==r)return tree[idx];
int mid=(l+r)/2;
return min(tree[idx],min(query(l,mid,idx*2,q),query(mid+1,r,idx*2+1,q)));
}
}t;
struct segment_tree1
{
int tree[4*MAXN];
void update(int l,int r,int idx,int q,int val)
{
if(l>q)return;
if(r<q)return;
if(l==r)
{
tree[q]=val;
return;
}
int mid=(l+r)/2;
update(l,mid,idx*2,q,val);
update(mid+1,r,idx*2+1,q,val);
tree[idx]=max(tree[idx*2],tree[idx*2+1]);
}
int query(int l,int r,int idx,int ql,int qr)
{
if(l>qr)return 0;
if(r<ql)return 0;
if(l>=ql&&r<=qr)return tree[idx];
int mid=(l+r)/2;
return max(query(l,mid,idx*2,ql,qr),query(mid+1,r,idx*2+1,ql,qr));
}
}t1;
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
vector<pair<int,int> >real;
//cout<<"?\n";
for(int i=1;i<N;i++)
{
real_positions1.update(i,1);
real_positions2.update(i,1);
}
//cout<<"?\n";
for(int i=0;i<C;i++)
{
int s1=real_positions1.get_position(S[i]);
int e1=real_positions2.get_position(E[i]);
real.push_back({s1,e1});
real_positions1.update(s1+1,E[i]-S[i]);
real_positions2.update(s1,E[i]-S[i]);
}
return 0;
/*for(auto xd:real)
{
cout<<xd.first<<" "<<xd.second<<endl;
}*/
//cout<<"?\n";
//reverse(real.begin(),real.end());
t.build(0,N-1,1);
t.update(0,N-1,1,real.back().first,real.back().second,real.size());
par[real.size()+1][0]=0;
for(int i=real.size()-2;i>=0;i--)
{
int br=t.query(0,N-1,1,real[i].first);
par[i+1][0]=br;
not_leaf[br]=1;
t.update(0,N-1,1,real[i].first,real[i].second,i+1);
}
for(int step=1;step<lg;step++)
{
for(int i=1;i<=C;i++)
{
par[i][step]=par[par[i][step-1]][step-1];
}
}
/*for(int i=1;i<=C;i++)
{
cout<<"^^ "<<i<<" "<<par[i][0]<<endl;
}*/
for(int i=1;i<N;i++)
{
t1.update(0,N-1,1,i,K[i-1]);
}
int ans=0;
for(int i=0;i<N;i++)
{
//cout<<i<<endl;
int x=t.query(0,N-1,1,i);
//
int d=0;
for(int j=lg-1;j>=0;j--)
{
//cout<<" "<<j<<endl;
//cout<<" "<<x<<" "<<j<<" "<<par[x][j]<<endl;
if(par[x][j]==0)continue;
int f=par[x][j]-1;
//cout<<" "<<real[f].first<<" "<<real[f].second<<" "<<t1.query(0,N-1,1,real[f].first,real[f].second)<<endl;
if(t1.query(0,N-1,1,real[f].first,real[f].second)>=R)
{
continue;
}
x=par[x][j];
d+=(1<<j);
}
//cout<<"?\n";
ans=max(ans,d);
if(i==N-1)continue;
//cout<<" -\n";
t1.update(0,N-1,1,i,K[i]);
}
return ans;
}
/*
5 3 3
1
0
2
4
1 3
0 1
0 1
*/
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;
}