Submission #1169626

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1169626	2025-03-19 03:12:57	blackslex	Dancing Elephants (IOI11_elephants)	C++20	97 / 100	9014 ms	19348 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 "elephants.h"
#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int MxN = 1.5e5 + 5, MxK = 400;
int n, l, x[MxN], cnt, z[MxN];
vector<int> v[MxK];
vector<pii> dp[MxK];
multiset<int> ms[MxK];
void upd (int idx) {
  v[idx].clear();
  for (auto &e: ms[idx]) v[idx].emplace_back(e);
  if (v[idx].empty()) return;
  // cerr << "UPD " << idx << '\n';
  // for (auto &e: v[idx]) cerr << e << ' '; cerr << '\n';
  int csz = v[idx].size();
  dp[idx].resize(csz);
  deque<int> dq;
  for (int i = csz - 1; i >= 0; i--) {
    while (dq.size() > 1 && v[idx][dq.end()[-2]] > v[idx][i] + l) dq.pop_back();
    if (dq.empty() || v[idx][i] + l >= v[idx][dq.back()]) {
      dp[idx][i] = {v[idx][i] + l, 1};
    } else {
      dp[idx][i] = {dp[idx][dq.back()].first, dp[idx][dq.back()].second + 1};
    }
    dq.emplace_front(i);
  }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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