Submission #1239363

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239363		pcp	Jousting tournament (IOI12_tournament)	C++20	0 / 100	1 ms	1860 KiB

tournament

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;
const int NN=100000;
int tree[4*NN];

void in_updt(int node, int l, int r){
  int m = (l + r)/2;
  if (l == r){
    
    tree[node]=1;
    return;

  }

  in_updt(node*2, l, m);
  in_updt(node*2 + 1, m+1, r);

  tree[node] = tree[node*2]+tree[node*2+1];
}


void update(int node, int l, int r, int x, int y){
  int m = (l + r)/2;
  if (l>y || r<=x)return;


  if (l == r && l >x && r<=y ){
    tree[node]=0;
    return;
  }


  update(node*2, l, m, x, y );
  update(node*2 + 1, m+1, r, x, y );

  tree[node] = tree[node*2]+tree[node*2+1];
}


pair<int,int> query(int node, int l, int r, int x, int y){
  int m = (l + r)/2;

  if (l==r || (x<0 && y>NN ))return {l,r};
  

  if (0==x)return {l,query(node,l,r,(2*NN)*-1,y).second};

  if (tree[node]==y)return {query(node,l,r,x,2*NN).first,r};

  if (tree[node*2]==x)return {m+1,query(node*2+1,m+1,r,x-tree[node*2],y-tree[node*2]).second};

  if (tree[node*2] > y)return query(node*2,l,m,x,y);

  if (tree[node*2]<=x)return query(node*2+1,m+1,r,x-tree[node*2],y-tree[node*2]);

  return {query(node*2,l,m,x,2*NN).first,   query(node*2+1,m+1,r,(2*NN)*-1,y-tree[node*2]).second };
}


int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
  memset(tree, 0, sizeof tree);
  in_updt(1,0,N-1);

  int mayores[N+10];
  int c=0;
  mayores[0]=0;
  for (int i = 1 ; i < N;++i){
    if (K[i-1]>R)c++;
    mayores[i]=c;
    //cout<<c<<" ";
  }
  mayores[N]=c;
  //cout<<endl;

  //
  //if (1) return 0;

  //

  int zipline[N+10];
  memset(zipline, 0, sizeof zipline);


  for (int i = 0 ; i < C; ++i){
    pair<int,int> range = query(1,0,N-1,S[i],E[i]);
    //cout<<S[i]<<" "<<E[i]<<" -> "<<range.first<<" "<<range.second<<endl;
    

    if (mayores[range.first] == mayores[range.second] || range.first==range.second){
      zipline[range.first]+=1;
      zipline[range.second+1]-=1;
    }




    update(1,0,N-1,S[i],E[i]);
    ///for (int i = 0; i < 20;++i)cout<<tree[i]<<" ";
    ////cout<<endl;
  }

  c=0;
  int maxx=0;
  int maxxwho=0;

  for (int i = 0 ; i < N;++i){

    c+=zipline[i];
    //cout<<c<<" ";


    if (c>maxx){
      maxx=c;
      maxxwho=i;
    }


  }

  //cout<<endl;


  return maxxwho;
  

}

• Subtask 1: 0 / 17
• Subtask 2: 0 / 32
• Subtask 3: 0 / 51