Submission #600165

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
600165	2022-07-20T13:52:46 Z	MilosMilutinovic	Dancing Elephants (IOI11_elephants)	C++14	97 / 100	9000 ms	11460 KB

elephants

/**
 *    author:  wxhtzdy
 *    created: 20.07.2022 11:59:55
**/
#include "elephants.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX = 150005;
const int BLOCK = sqrt(MAX);

int n, l, x[MAX], cnt[MAX], pos[MAX];
int id[MAX], order[MAX];

vector<int> idx[MAX / BLOCK + 5];

void BuildBlock(int i) {
  int sz = (int) idx[i].size();
  int ptr = sz - 1;    
  for (int j = sz - 1; j >= 0; j--) {
    if (x[idx[i][sz - 1]] - x[idx[i][j]] <= l) {
      cnt[idx[i][j]] = 1;
      pos[idx[i][j]] = x[idx[i][j]] + l;
    } else { 
      while (x[idx[i][ptr]] - x[idx[i][j]] > l) {
        ptr -= 1;
      }
      cnt[idx[i][j]] = cnt[idx[i][ptr + 1]] + 1;
      pos[idx[i][j]] = pos[idx[i][ptr + 1]];
    }                              
  }
}

void Build() {     
  for (int i = 0; i < n; i++) {
    order[i] = i;
  }
  sort(order, order + n, [&](int i, int j) {
    return x[i] < x[j];
  });
  for (int i = 0; i <= n / BLOCK; i++) {
    idx[i].clear();
  }
  for (int i = 0; i < n; i++) {
    id[order[i]] = i / BLOCK;
    idx[id[order[i]]].push_back(order[i]);
  }
  for (int i = 0; i <= n / BLOCK; i++) {
    BuildBlock(i);
  }
}

int Q;

int update(int i, int y) {
  ++Q;
  x[i] = y;
  if (Q == BLOCK) {
    Build();
    Q = 0;
  } else {
    vector<int> b;
    for (int j = 0; j < (int) idx[id[i]].size(); j++) {
      if (idx[id[i]][j] != i) {      
        b.push_back(idx[id[i]][j]);
      }
    }
    idx[id[i]] = b;
    BuildBlock(id[i]);
    b.clear();
    id[i] = 0;
    for (int j = n / BLOCK; j >= 0; j--) {
      if (!idx[j].empty() && x[idx[j][0]] <= x[i]) {
        id[i] = j;
        break;
      } 
    }        
    if (idx[id[i]].empty() || x[idx[id[i]].back()] < y) {
      idx[id[i]].push_back(i);
    } else {
      vector<int> b;    
      for (int j = 0; j < (int) idx[id[i]].size(); j++) {
        if (y <= x[idx[id[i]][j]]) {
          b.push_back(i);
          y = (int) 1.01e9;
          j -= 1;
        } else {
          b.push_back(idx[id[i]][j]);
        }
      }
      idx[id[i]] = b;
    }
    BuildBlock(id[i]);
  } 
  int ans = 0, R = -1;
  for (int j = 0; j <= n / BLOCK; j++) {
    if (idx[j].empty() || x[idx[j].back()] <= R) {
      continue;
    }                                          
    int low = 0, high = (int) idx[j].size() - 1, at = 0;
    while (low <= high) {
      int mid = low + high >> 1;
      if (x[idx[j][mid]] > R) {
        at = mid;
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
    ans += cnt[idx[j][at]];
    R = pos[idx[j][at]];
  }
  return ans; 
}

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

Compilation message

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:103:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  103 |       int mid = low + high >> 1;
      |                 ~~~~^~~~~~

Subtask #1

10.0 / 10.0

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

Subtask #2

16.0 / 16.0

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

Subtask #3

24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	575 ms	1288 KB	Output is correct
8	Correct	608 ms	1428 KB	Output is correct
9	Correct	775 ms	2360 KB	Output is correct
10	Correct	698 ms	2372 KB	Output is correct
11	Correct	695 ms	2368 KB	Output is correct
12	Correct	1381 ms	2380 KB	Output is correct
13	Correct	687 ms	2368 KB	Output is correct

Subtask #4

47.0 / 47.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	575 ms	1288 KB	Output is correct
8	Correct	608 ms	1428 KB	Output is correct
9	Correct	775 ms	2360 KB	Output is correct
10	Correct	698 ms	2372 KB	Output is correct
11	Correct	695 ms	2368 KB	Output is correct
12	Correct	1381 ms	2380 KB	Output is correct
13	Correct	687 ms	2368 KB	Output is correct
14	Correct	841 ms	1820 KB	Output is correct
15	Correct	839 ms	1840 KB	Output is correct
16	Correct	2019 ms	2596 KB	Output is correct
17	Correct	2318 ms	3192 KB	Output is correct
18	Correct	2654 ms	3188 KB	Output is correct
19	Correct	1629 ms	3192 KB	Output is correct
20	Correct	2654 ms	4532 KB	Output is correct
21	Correct	2593 ms	5184 KB	Output is correct
22	Correct	1452 ms	4776 KB	Output is correct

Subtask #5

0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	575 ms	1288 KB	Output is correct
8	Correct	608 ms	1428 KB	Output is correct
9	Correct	775 ms	2360 KB	Output is correct
10	Correct	698 ms	2372 KB	Output is correct
11	Correct	695 ms	2368 KB	Output is correct
12	Correct	1381 ms	2380 KB	Output is correct
13	Correct	687 ms	2368 KB	Output is correct
14	Correct	841 ms	1820 KB	Output is correct
15	Correct	839 ms	1840 KB	Output is correct
16	Correct	2019 ms	2596 KB	Output is correct
17	Correct	2318 ms	3192 KB	Output is correct
18	Correct	2654 ms	3188 KB	Output is correct
19	Correct	1629 ms	3192 KB	Output is correct
20	Correct	2654 ms	4532 KB	Output is correct
21	Correct	2593 ms	5184 KB	Output is correct
22	Correct	1452 ms	4776 KB	Output is correct
23	Correct	5457 ms	11404 KB	Output is correct
24	Correct	5468 ms	11416 KB	Output is correct
25	Correct	4261 ms	11424 KB	Output is correct
26	Correct	5377 ms	11432 KB	Output is correct
27	Correct	6538 ms	11284 KB	Output is correct
28	Correct	1985 ms	5172 KB	Output is correct
29	Correct	2081 ms	5176 KB	Output is correct
30	Correct	2223 ms	5180 KB	Output is correct
31	Correct	2248 ms	5176 KB	Output is correct
32	Correct	5300 ms	10852 KB	Output is correct
33	Correct	4625 ms	10188 KB	Output is correct
34	Correct	4966 ms	11072 KB	Output is correct
35	Correct	3927 ms	11360 KB	Output is correct
36	Correct	2763 ms	10844 KB	Output is correct
37	Correct	8361 ms	11460 KB	Output is correct
38	Correct	4944 ms	10068 KB	Output is correct
39	Correct	6961 ms	11104 KB	Output is correct
40	Correct	5105 ms	10104 KB	Output is correct
41	Execution timed out	9061 ms	10844 KB	Time limit exceeded
42	Halted	0 ms	0 KB	-