oj.uz

Submission #17363

# Submission time Handle Problem Language Result Execution time Memory
17363 2015-11-27T03:25:33 Z comet Jousting tournament (IOI12_tournament) C++
49 / 100
 1000 ms 5144 KB 
	
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
 
struct RMQ{
  vector<int> tree;
  int sz;
  void init(int n){
    for(sz=1;sz<n;sz<<=1);
    tree.resize(2*sz+1);
  }
  void update(int x,int c){
    x+=sz;
    tree[x]=c;
    x>>=1;
    while(x){
      tree[x]=max(tree[x*2],tree[x*2+1]);
      x>>=1;
    }
  }
  int query(int L,int R){
    L+=sz,R+=sz;
    int ret=0;
    while(L<R){
      if(L&1)ret=max(ret,tree[L++]);
      if(~R&1)ret=max(ret,tree[R--]);
      L>>=1,R>>=1;
    }
    if(L==R)ret=max(ret,tree[L]);
    return ret;
  }
}rmq;
 
struct BIT{
  vector<int> tree;
  int sz;
  void init(int n){
    for(sz=1;sz<n;sz<<=1);
    tree.resize(sz+1);
  }
  void add(int x,int c){
    x++;
    while(x<=sz){
      tree[x]+=c;
      x+=x&-x;
    }
  }
  int sum(int x){
    if(x<0)return 0;
    x++;
    int ret=0;
    while(x){
      ret+=tree[x];
      x-=x&-x;
    }
    return ret;
  }
  int query(int x){
    if(x<0)return -1;
    x++;
    int p=0;
      for(int i=sz/2;i;i>>=1){
          if(tree[p+i]<x){
              x-=tree[p+i];
              p+=i;
          }
      }
      return p;
  }
}bit;
 
int nxt[100010];
bool chk[100010];
/*
int find(int x){
  return nxt[x]=(nxt[x]==x?x:find(nxt[x]));
}
*/
int find(int x){
  x++;
  int p=0;
  while(x){
    if(!chk[p])x--;
    p++;
  }
  return p-1;
}
 
int a[100010];
 
int GetBestPosition(int N, int C, int M, int *K, int *S, int *E){
   
  rmq.init(N);
  bit.init(N);
 
  for(int i=0;i<N-1;i++){
    rmq.update(i,K[i]);
    bit.add(i,1);
    nxt[i]=i;
  }
  bit.add(N-1,1);
  nxt[N-1]=N-1;
 
  for(int i=0;i<C;i++){
  //  puts("kth");
    //for(int j=0;j<N-1;j++)printf("%d ",bit.query(j));
      //puts("");
     
    int L=bit.query(S[i]-1)+1;
    int R=bit.query(E[i])-1;
    R=min(R,max(0,N-2));
 
    int LL=0,RR=0;
    LL=find(S[i]-1)+1;
    RR=find(E[i])-1;
 
 //   printf("%d %d , %d %d\n",L,R,LL,RR);
 //   printf("max = %d",rmq.query(L,R));
 
    if(rmq.query(L,R)<M){
      a[L]++;
      a[R+1]--;
    }
 
    for(int i=L;i<=R;i++){
      if(chk[i])continue;
      bit.add(i,-1);
      chk[i]=1;
    }
 
//    puts("");
//    printf("L=%d R=%d\n",L,R);
//    for(int i=0;i<N-1;i++)printf("%d ",chk[i]);
//    for(int i=0;i<N-1;i++)printf("%d ",bit.sum(i)-bit.sum(i-1));
//    puts("");puts("");
 
  }
 
  int ans=0,Max=0;
 
  for(int i=0;i<N-1;i++){
    if(i)a[i]+=a[i-1];
 //   printf("%d ",a[i]);
    if(Max<a[i]){
      Max=a[i];
      ans=i;
    }
  }
//  puts("");
 
  return ans;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2460 KB Output is correct
2 Correct 0 ms 2460 KB Output is correct
3 Correct 0 ms 2460 KB Output is correct
4 Correct 0 ms 2460 KB Output is correct
5 Correct 0 ms 2460 KB Output is correct
6 Correct 1 ms 2460 KB Output is correct
7 Correct 0 ms 2460 KB Output is correct
8 Correct 0 ms 2460 KB Output is correct
9 Correct 0 ms 2460 KB Output is correct
10 Correct 0 ms 2460 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2460 KB Output is correct
2 Correct 16 ms 2616 KB Output is correct
3 Correct 0 ms 2460 KB Output is correct
4 Correct 6 ms 2616 KB Output is correct
5 Correct 9 ms 2608 KB Output is correct
6 Correct 3 ms 2600 KB Output is correct
7 Correct 12 ms 2612 KB Output is correct
8 Correct 8 ms 2616 KB Output is correct
9 Correct 0 ms 2460 KB Output is correct
10 Correct 0 ms 2616 KB Output is correct

Subtask #3
0.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3680 KB Output is correct
2 Execution timed out 1000 ms 5144 KB Program timed out
3 Halted 0 ms 0 KB -