| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 43808 | gnoor | 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 <cstdio>
#include <cassert>
#include <algorithm>
#include <vector>
using namespace std;
struct node {
int val;
vector<node*> chd;
node* par;
bool isSuper;
node(int x) {
val=x;
//par=0;
}
};
node* null = new node(-1);
int bit[100100];
node* aux[100100];
node* leaf[100100];
node* root;
void add(int idx,int val) {
while (idx<100100) {
bit[idx]+=val;
idx+=(idx&-idx);
}
}
int get(int idx) {
int ans=0;
while (idx) {
ans+=bit[idx];
idx-=(idx&-idx);
}
return ans;
}
int n;
int get2(int idx) {
int l=1;
int r=n;
while (l<r) {
int m=(l+r)>>1;
if (get(m)>=idx) r=m;
else l=m+1;
}
return l;
}
int cnt=0;
int ans=0;
node* buildTree(vector<node*> &a,int ll,int rr) {
if (ll+1==rr) return a[ll];
int mm=(ll+rr)>>1;
auto l = buildTree(a,ll,mm);
auto r = buildTree(a,mm,rr);
node* neww = new node(max(l->val,r->val));
neww->par=null;
l->par=neww;
r->par=neww;
neww->chd.push_back(l);
neww->chd.push_back(r);
return neww;
}
void construct(node* idx) {
//assert(idx!=0);
//printf("eiii\n");
//printf("ei %d\n",idx->val);
if (idx->chd.size()==0) return;
for (int i=0;i<(int)idx->chd.size();i++) {
construct(idx->chd[i]);
}
int mm=idx->chd.size()/2;
node* l = buildTree(idx->chd,0,mm);
node* r = buildTree(idx->chd,mm,idx->chd.size());
l->par=idx;
r->par=idx;
idx->chd.clear();
idx->chd.push_back(l);
idx->chd.push_back(r);
}
int r;
void upTree(node* idx) {
assert(idx!=0);
int mx=-1;
for (int i=0;i<(int)idx->chd.size();i++) {
mx=max(mx,idx->chd[i]->val);
}
if (idx->isSuper) {
if (idx->val==r) cnt--;
if (mx==r) cnt++;
}
idx->val=mx;
if (idx->par==null) return;
upTree(idx->par);
}
void printTree(node* idx) {
printf("## %d\n>> ",idx->val);
for (int i=0;i<(int)idx->chd.size();i++) {
printf("%d ",idx->chd[i]->val);
}
printf("\n");
for (int i=0;i<(int)idx->chd.size();i++) {
printTree(idx->chd[i]);
}
}
int main () {
int c;
scanf("%d%d%d",&n,&c,&r);
aux[1]=leaf[1]=new node(r);
int x;
add(1,1);
for (int i=2;i<=n;i++) {
scanf("%d",&x);
aux[i]=leaf[i]=new node(x);
add(i,1);
}
int s,e;
for (int i=0;i<c;i++) {
scanf("%d%d",&s,&e);
s++;
e++;
node* neww=new node(0);
int mx=-1;
for (int j=s;j<=e;j++) {
node* xx = aux[get2(j)];
xx->par=neww;
neww->chd.push_back(xx);
mx=max(mx,xx->val);
//printf("**%d ",xx->val);
}
aux[get2(s)]=neww;
for (int j=e;j>s;j--) {
add(get2(j),-1);
}
//printf("\n");
neww->par=null;
neww->isSuper=true;
neww->val=mx;
//add(s+1,e-s);
if (mx==r) cnt++;
}
ans=cnt;
int ansId=0;
root=aux[1];
//printf("yay\n");
//printTree(root);
construct(root);
//printf("yo\n");
for (int i=1;i<n;i++) {
int a=leaf[i]->val;
int b=leaf[i+1]->val;
leaf[i]->val=b;
upTree(leaf[i]->par);
leaf[i+1]->val=a;
upTree(leaf[i+1]->par);
if (cnt>ans) {
ans=cnt;
ansId=i;
}
}
printf("%d\n",ansId);
return 0;
}