Submission #1240068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240068		guanex	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 || tree[node]==0)return;


  if (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, bool lx, bool ly){
  int m = (l + r)/2;

  if (l==r)return {l,r};

  if (lx && ly){

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

    if (tree[node*2]<x)return query(node*2+1, m+1, r, x-tree[node*2],y-tree[node*2],1,1);
    //cout<<tree[node*2]<<" "<<x<<endl;
    return {query(node*2,l,m,x,0,1,0).first,query(node*2+1, m+1, r, 0,y-tree[node*2],0,1).second  };

  }else if (lx){

    //cout<<l<<" "<<r<<" "<<tree[node*2]<<" "<<x<<endl;



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

    return query(node*2,l,m,x,0,1,0);

  }else if (ly){
    
    if (tree[node*2]>=y)return query(node*2,l,m,0,y,0,1);
    else return query(node*2+1, m+1,r, 0, y-tree[node*2],0,1);

  }else return {-1,-1};

}


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;
  mayores[N+1]=c;
  //cout<<endl;

  //
  //if (1) return 0;

  //

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

  //for (int i = 1; i < 20;++i)cout<<tree[i]<<" ";
  //cout<<endl;


  for (int i = 0 ; i < C; ++i){
    pair<int,int> range = query(1,0,N-1,S[i]+1,E[i]+1,1,1);

    //cout<<S[i]<<" "<<E[i]<<" -> "<<range.first<<" "<<range.second<<" ->";
    

    if (mayores[range.first] == mayores[range.second-1]){
      zipline[range.first]+=1;
      zipline[range.second+1]-=1;
      //cout<<"[AC]";
    }//else cout<<"[WA]";
    //cout<<endl;



    update(1,0,N-1,range.first+1,range.second);
    //for (int i = 1; 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