#include "bits/stdc++.h"
using namespace std;
//sad; long long double doesn't exist
using ld = long double;
//imagine a language where int = long
#define long long long
//typing too hard
#define endl "\n"
#define sz(x) int(x.size())
const int maxn = 150000, bsize = 400, m = maxn / bsize + 1;
int n, l, cnt = 0;
int arr[maxn], order[maxn];
vector<int> buc[m];
vector<pair<int, int>> vals[m];
void maintain(int ind) {
int n = sz(buc[ind]);
vals[ind].resize(n);
int j = n - 1;
for(int i = n - 1; i >= 0; i--) {
while(j >= 0 && buc[ind][j] > buc[ind][i] + l) {
j--;
}
if(j + 1 == n) {
vals[ind][i] = {buc[ind][i], 1};
}else {
vals[ind][i] = vals[ind][j + 1];
vals[ind][i].second++;
}
}
}
void merge() {
int ind = 0;
for(auto &i: buc) {
for(auto &j: i) {
arr[ind++] = j;
}
}
assert(ind == n);
}
void build() {
for(int i = 0, ind = 0; i < n; i += bsize, ind++) {
buc[ind].clear();
buc[ind].insert(buc[ind].end(), arr + i, arr + min(n, i + bsize));
}
for(int i = 0; i < m; i++) {
maintain(i);
}
}
void init(int _n, int _l, int _arr[]) {
n = _n;
l = _l;
for(int i = 0; i < n; i++) {
arr[i] = order[i] = _arr[i];
}
build();
}
void remove(int x) {
for(int i = 0; i < m; i++) {
if(sz(buc[i]) && buc[i].back() >= x) {
buc[i].erase(lower_bound(begin(buc[i]), end(buc[i]), x));
maintain(i);
return;
}
}
assert(false);
}
void insert(int x) {
int last = -1;
for(int i = 0; i < m; i++) {
if(sz(buc[i])) {
last = i;
if(buc[i].back() >= x) {
buc[i].insert(lower_bound(begin(buc[i]), end(buc[i]), x), x);
maintain(i);
return;
}
}
}
assert(last != -1);
buc[last].push_back(x);
maintain(last);
}
int update(int ind, int x) {
if(++cnt == bsize) {
merge();
build();
cnt = 0;
}
remove(order[ind]);
insert(x);
order[ind] = x;
int prev = INT_MIN;
int ans = 0;
for(int i = 0; i < m; i++) {
auto it = lower_bound(begin(buc[i]), end(buc[i]), prev + l + 1);
if(it != buc[i].end()) {
auto cur = vals[i][it - buc[i].begin()];
ans += cur.second;
prev = cur.first;
}
}
return ans;
}
struct solver {
int n, l;
int arr[maxn];
solver(int n, int l, int arr[]): n(n), l(l) {
for(int i = 0; i < n; i++) {
this->arr[i] = arr[i];
}
}
int update(int ind, int x) {
arr[ind] = x;
vector<int> tmp(arr, arr + n);
sort(begin(tmp), end(tmp));
int ans = 0, prev = INT_MIN;
for(auto &i: tmp) {
if(i > prev + l) {
prev = i;
ans++;
}
}
return ans;
}
};
void reset() {
cnt = 0;
memset(arr, 0, sizeof(arr));
for(int i = 0; i < m; i++) {
buc[i].clear();
vals[i].clear();
}
}
void stress() {
mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
auto rint = [&mt](int l, int r) {return l + mt() % (r - l + 1);};
while(true) {
reset();
int n = rint(2, 5), l = rint(0, 100), q = rint(2, 5);
int arr[n];
for(int i = 0; i < n; i++) {
arr[i] = rint(0, 100);
}
sort(arr, arr + n);
init(n, l, arr);
solver s(n, l, arr);
vector<pair<int, int>> qs;
while(q--) {
int ind = rint(0, n - 1), x = rint(0, 100);
qs.emplace_back(ind, x);
int a = update(ind, x), b = s.update(ind, x);
if(a != b) {
cerr << n << " " << l << endl;
for(auto &i: arr) {
cerr << i << " ";
}
cerr << endl;
for(auto &i: qs) {
cerr << i.first << " " << i.second << endl;
}
cerr << a << " " << b << endl << endl;
}
}
}
}
void grade() {
reset();
int n, l, q;
cin >> n >> l >> q;
int arr[n];
for(int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
int ii[q], yy[q], sol[q];
for(int i = 0; i < q; i++) {
scanf("%d%d%d", &ii[i], &yy[i], &sol[i]);
}
init(n, l, arr);
for(int i = 0; i < q; i++) {
int ans = update(ii[i], yy[i]);
if(ans != sol[i]) {
printf("Incorrect. In %d-th move, answered %d (%d expected).\n", i + 1, ans, sol[i]);
return;
}
}
printf("Correct.\n");
}
int main1412() {
// stress();
// freopen("elephants-test/subtask4/grader.in.1", "r", stdin);
freopen("input.txt", "r", stdin);
grade();
using namespace filesystem;
for(auto &subtask: directory_iterator("elephants-test")) {
char last = subtask.path().string().back();
if(isdigit(last)) {
printf("Grading subtask %d:\n", last - '0');
map<int, string> tests;
for(auto &test: directory_iterator(subtask)) {
string path = test.path().string();
auto ind = path.find("grader.in.");
if(ind != string::npos) {
tests[stoi(path.substr(ind + 10))] = path;
}
}
for(auto &test: tests) {
printf("Grading case %d: ", test.first);
freopen(test.second.c_str(), "r", stdin);
grade();
}
printf("\n");
}
}
}
Compilation message
elephants.cpp: In function 'int main1412()':
elephants.cpp:236:1: warning: no return statement in function returning non-void [-Wreturn-type]
236 | }
| ^
elephants.cpp: In function 'void grade()':
elephants.cpp:192:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
192 | scanf("%d", &arr[i]);
| ~~~~~^~~~~~~~~~~~~~~
elephants.cpp:196:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
196 | scanf("%d%d%d", &ii[i], &yy[i], &sol[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'int main1412()':
elephants.cpp:213:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
213 | freopen("input.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
elephants.cpp:230:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
230 | freopen(test.second.c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
353 ms |
2412 KB |
Output is correct |
8 |
Correct |
375 ms |
2668 KB |
Output is correct |
9 |
Correct |
357 ms |
3992 KB |
Output is correct |
10 |
Correct |
349 ms |
3436 KB |
Output is correct |
11 |
Correct |
309 ms |
3436 KB |
Output is correct |
12 |
Correct |
607 ms |
4332 KB |
Output is correct |
13 |
Correct |
323 ms |
3308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
353 ms |
2412 KB |
Output is correct |
8 |
Correct |
375 ms |
2668 KB |
Output is correct |
9 |
Correct |
357 ms |
3992 KB |
Output is correct |
10 |
Correct |
349 ms |
3436 KB |
Output is correct |
11 |
Correct |
309 ms |
3436 KB |
Output is correct |
12 |
Correct |
607 ms |
4332 KB |
Output is correct |
13 |
Correct |
323 ms |
3308 KB |
Output is correct |
14 |
Correct |
355 ms |
3308 KB |
Output is correct |
15 |
Correct |
547 ms |
3436 KB |
Output is correct |
16 |
Correct |
1039 ms |
4972 KB |
Output is correct |
17 |
Correct |
1072 ms |
5740 KB |
Output is correct |
18 |
Correct |
1149 ms |
5740 KB |
Output is correct |
19 |
Correct |
525 ms |
5100 KB |
Output is correct |
20 |
Correct |
1075 ms |
5828 KB |
Output is correct |
21 |
Correct |
1034 ms |
5868 KB |
Output is correct |
22 |
Correct |
525 ms |
4460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
353 ms |
2412 KB |
Output is correct |
8 |
Correct |
375 ms |
2668 KB |
Output is correct |
9 |
Correct |
357 ms |
3992 KB |
Output is correct |
10 |
Correct |
349 ms |
3436 KB |
Output is correct |
11 |
Correct |
309 ms |
3436 KB |
Output is correct |
12 |
Correct |
607 ms |
4332 KB |
Output is correct |
13 |
Correct |
323 ms |
3308 KB |
Output is correct |
14 |
Correct |
355 ms |
3308 KB |
Output is correct |
15 |
Correct |
547 ms |
3436 KB |
Output is correct |
16 |
Correct |
1039 ms |
4972 KB |
Output is correct |
17 |
Correct |
1072 ms |
5740 KB |
Output is correct |
18 |
Correct |
1149 ms |
5740 KB |
Output is correct |
19 |
Correct |
525 ms |
5100 KB |
Output is correct |
20 |
Correct |
1075 ms |
5828 KB |
Output is correct |
21 |
Correct |
1034 ms |
5868 KB |
Output is correct |
22 |
Correct |
525 ms |
4460 KB |
Output is correct |
23 |
Correct |
2646 ms |
12252 KB |
Output is correct |
24 |
Correct |
3089 ms |
12268 KB |
Output is correct |
25 |
Correct |
2205 ms |
11756 KB |
Output is correct |
26 |
Correct |
2561 ms |
10756 KB |
Output is correct |
27 |
Correct |
2477 ms |
10608 KB |
Output is correct |
28 |
Correct |
1265 ms |
5484 KB |
Output is correct |
29 |
Correct |
1203 ms |
5356 KB |
Output is correct |
30 |
Correct |
1245 ms |
5356 KB |
Output is correct |
31 |
Correct |
1212 ms |
5356 KB |
Output is correct |
32 |
Correct |
1701 ms |
10188 KB |
Output is correct |
33 |
Correct |
1791 ms |
9580 KB |
Output is correct |
34 |
Correct |
1998 ms |
10396 KB |
Output is correct |
35 |
Correct |
1765 ms |
12396 KB |
Output is correct |
36 |
Correct |
1257 ms |
10092 KB |
Output is correct |
37 |
Correct |
2715 ms |
12228 KB |
Output is correct |
38 |
Correct |
1823 ms |
9452 KB |
Output is correct |
39 |
Correct |
1874 ms |
10604 KB |
Output is correct |
40 |
Correct |
1989 ms |
9660 KB |
Output is correct |
41 |
Correct |
3609 ms |
12080 KB |
Output is correct |
42 |
Correct |
3657 ms |
12324 KB |
Output is correct |