답안 #116618

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-