oj.uz

Submission #17365

# Submission time Handle Problem Language Result Execution time Memory
17365 2015-11-27T03:35:51 Z comet Jousting tournament (IOI12_tournament) C++
100 / 100
 76 ms 5680 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 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++){
 
    int L=bit.query(S[i]-1)+1;
    int R=bit.query(E[i])-1;
    R=min(R,max(0,N-2));
 
    if(rmq.query(L,R)<M){
      a[L]++;
      a[R+1]--;
    }
 
    for(int i=L;i<=R;i++){
      i=find(i);
      if(i>R)continue;
      bit.add(i,-1);
      nxt[i]=i+1;
    }
 
  }
 
  int ans=0,Max=0;
 
  for(int i=0;i<N-1;i++){
    if(i)a[i]+=a[i-1];
    if(Max<a[i]){
      Max=a[i];
      ans=i;
    }
  }
  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 0 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 0 ms 2616 KB Output is correct
3 Correct 0 ms 2460 KB Output is correct
4 Correct 4 ms 2616 KB Output is correct
5 Correct 0 ms 2608 KB Output is correct
6 Correct 3 ms 2600 KB Output is correct
7 Correct 4 ms 2612 KB Output is correct
8 Correct 4 ms 2616 KB Output is correct
9 Correct 0 ms 2460 KB Output is correct
10 Correct 4 ms 2616 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3680 KB Output is correct
2 Correct 72 ms 5148 KB Output is correct
3 Correct 33 ms 5680 KB Output is correct
4 Correct 73 ms 5148 KB Output is correct
5 Correct 76 ms 5112 KB Output is correct
6 Correct 65 ms 4884 KB Output is correct
7 Correct 67 ms 5148 KB Output is correct
8 Correct 71 ms 5148 KB Output is correct
9 Correct 30 ms 5596 KB Output is correct
10 Correct 30 ms 4396 KB Output is correct