Submission #947324

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
947324	2024-03-15 21:59:38	MinaRagy06	Dancing Elephants (IOI11_elephants)	C++17	100 / 100	2589 ms	23136 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>
using namespace std;
#define ll long long
#define SZ(x) (int) x.size()
int n, l;
const int N = 150'005, B = 400;
struct block {
  int n;
  vector<int> v;
  vector<array<int, 2>> dp;
  void build() {
    n = v.size();
    dp.resize(n);
    int p = n;
    for (int i = n - 1; i >= 0; i--) {
      while (p - 1 >= 0 && v[p - 1] >= v[i] + l) {
        p--;
      }
      if (v[i] + l <= v.back()) {
        dp[i] = {dp[p][0] + 1, dp[p][1]};
      } else {
        dp[i] = {1, v[i] + l};
      }
    }
  }
  void insert(int x) {
    v.push_back(x);
    for (int i = v.size() - 1; i - 1 >= 0; i--) {
      if (v[i] <= v[i - 1]) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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