Submission #14776

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
14776	2015-06-22 09:11:39	minsu	Dancing Elephants (IOI11_elephants)	C++14	100 / 100	6607 ms	22272 KiB

elephants

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
#include "elephants.h"
using namespace std;
#define MAXE 150051
#define BLOCK 400
int n, bn, l, ele[MAXE], tmp[MAXE], cooltime;
int p[BLOCK][BLOCK*2], sz[BLOCK][BLOCK*2], la[BLOCK][BLOCK*2], pn[BLOCK], pl[BLOCK];
void calc(int b){
  for(int i=pn[b]-1; i>=0; i--){
    int nxt = lower_bound( p[b]+i+1, p[b]+pn[b], p[b][i] + l + 1 ) - p[b];
    if( nxt == pn[b] ) sz[b][i] = 1, la[b][i] = p[b][i] + l + 1;
    else sz[b][i] = sz[b][nxt] + 1, la[b][i] = la[b][nxt];
  }
}
void mkblock( int X[] ){
  for(int i=0; i<bn; i++) pn[i] = 0;
  for(int i=0; i<n; i++){
    int b = i / BLOCK;
    int& bs = pn[b];
    p[b][bs++] = X[i];
  } bn = ( n-1 ) / BLOCK + 1;
  for(int i=0; i<bn; i++)
    calc(i), pl[i] = p[i][pn[i]-1];
}
void init(int N, int L, int X[]){
  n = N; l = L;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3