oj.uz

Submission #17359

# Submission time Handle Problem Language Result Execution time Memory
17359 2015-11-27T02:28:41 Z comet Jousting tournament (IOI12_tournament) C++
17 / 100
 24 ms 3616 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 n,sz;
  void init(int n_){
    n=n_;
    for(sz=1;sz<n;sz<<=1);
    tree.resize(n+1);
  }
  void add(int x,int c){
    x++;
    while(x<=n){
      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 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;
  }
  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,N-2);

//    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 ",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 1 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 1 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
0.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2460 KB Output is correct
2 Correct 14 ms 2600 KB Output is correct
3 Correct 0 ms 2460 KB Output is correct
4 Correct 7 ms 2600 KB Output is correct
5 Correct 10 ms 2596 KB Output is correct
6 Runtime error 2 ms 2456 KB SIGSEGV Segmentation fault
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 3616 KB SIGSEGV Segmentation fault
2 Halted 0 ms 0 KB -