Submission #116618

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
116618	2019-06-13T05:45:16 Z	dragonslayerit	Dancing Elephants (IOI11_elephants)	C++14	50 / 100	9000 ms	1784 KB

elephants

#include "elephants.h"
#include <vector>
#include <algorithm>

const int INF=1e9+7;

int xs[100005];
int ys[100005];
int n;
int l;

void init(int N, int L, int X[])
{
  n=N;
  l=L;
  for(int i=0;i<N;i++){
    xs[i]=ys[i]=X[i];
  }
}

int update(int index, int new_val)
{
  int low=0,high=n-1;
  while(true){
    int mid=(low+high)/2;
    if(ys[mid]<xs[index]){
      low=mid+1;
    }else if(ys[mid]>xs[index]){
      high=mid-1;
    }else{
      int i=mid;
      while(i>0&&ys[i-1]>new_val){
	ys[i]=ys[i-1];
	i--;
      }
      while(i+1<n&&ys[i+1]<new_val){
	ys[i]=ys[i+1];
	i++;
      }
      ys[i]=new_val;
      break;
    }
  }
  xs[index]=new_val;
  
  int far=-INF;
  int cnt=0;
  for(int i=0;i<n;i++){
    if(ys[i]>far){
      far=ys[i]+l;
      cnt++;
    }
  }
  return cnt;
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	256 KB	Output is correct

Subtask #2

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	256 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct

Subtask #3

24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	256 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	1808 ms	1084 KB	Output is correct
8	Correct	2693 ms	1272 KB	Output is correct
9	Correct	2095 ms	1544 KB	Output is correct
10	Correct	3940 ms	1552 KB	Output is correct
11	Correct	3702 ms	1556 KB	Output is correct
12	Correct	6858 ms	1556 KB	Output is correct
13	Correct	4184 ms	1544 KB	Output is correct

Subtask #4

0 / 47.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	256 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	1808 ms	1084 KB	Output is correct
8	Correct	2693 ms	1272 KB	Output is correct
9	Correct	2095 ms	1544 KB	Output is correct
10	Correct	3940 ms	1552 KB	Output is correct
11	Correct	3702 ms	1556 KB	Output is correct
12	Correct	6858 ms	1556 KB	Output is correct
13	Correct	4184 ms	1544 KB	Output is correct
14	Correct	1462 ms	1408 KB	Output is correct
15	Correct	5349 ms	1476 KB	Output is correct
16	Execution timed out	9082 ms	1784 KB	Time limit exceeded
17	Halted	0 ms	0 KB	-

Subtask #5

0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	256 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	1808 ms	1084 KB	Output is correct
8	Correct	2693 ms	1272 KB	Output is correct
9	Correct	2095 ms	1544 KB	Output is correct
10	Correct	3940 ms	1552 KB	Output is correct
11	Correct	3702 ms	1556 KB	Output is correct
12	Correct	6858 ms	1556 KB	Output is correct
13	Correct	4184 ms	1544 KB	Output is correct
14	Correct	1462 ms	1408 KB	Output is correct
15	Correct	5349 ms	1476 KB	Output is correct
16	Execution timed out	9082 ms	1784 KB	Time limit exceeded
17	Halted	0 ms	0 KB	-