Submission #116613

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
116613	2019-06-13T05:33:21 Z	dragonslayerit	Dancing Elephants (IOI11_elephants)	C++14	50 / 100	9000 ms	3576 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)
{
  for(int i=0;i<n;i++){
    if(ys[i]==xs[index]){
      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	384 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	384 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	384 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	1939 ms	1112 KB	Output is correct
8	Correct	2931 ms	1168 KB	Output is correct
9	Correct	2244 ms	1548 KB	Output is correct
10	Correct	3604 ms	1548 KB	Output is correct
11	Correct	3541 ms	1548 KB	Output is correct
12	Correct	7656 ms	1572 KB	Output is correct
13	Correct	3879 ms	2668 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	384 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	1939 ms	1112 KB	Output is correct
8	Correct	2931 ms	1168 KB	Output is correct
9	Correct	2244 ms	1548 KB	Output is correct
10	Correct	3604 ms	1548 KB	Output is correct
11	Correct	3541 ms	1548 KB	Output is correct
12	Correct	7656 ms	1572 KB	Output is correct
13	Correct	3879 ms	2668 KB	Output is correct
14	Correct	1679 ms	2868 KB	Output is correct
15	Correct	5741 ms	2844 KB	Output is correct
16	Execution timed out	9072 ms	3576 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	384 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	1939 ms	1112 KB	Output is correct
8	Correct	2931 ms	1168 KB	Output is correct
9	Correct	2244 ms	1548 KB	Output is correct
10	Correct	3604 ms	1548 KB	Output is correct
11	Correct	3541 ms	1548 KB	Output is correct
12	Correct	7656 ms	1572 KB	Output is correct
13	Correct	3879 ms	2668 KB	Output is correct
14	Correct	1679 ms	2868 KB	Output is correct
15	Correct	5741 ms	2844 KB	Output is correct
16	Execution timed out	9072 ms	3576 KB	Time limit exceeded
17	Halted	0 ms	0 KB	-