#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else
#define cerr if(0)cout
#define debug(X) ;
#endif
using ll = long long;
#define all(v) (v).begin(), (v).end()
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
int n, l;
vector<int> x;
vector<int> idx;
void init(int _n, int _l, int _x[]) {
n = _n; l = _l;
for (int i = 0; i < n; ++i) x.eb(_x[i]);
idx.resize(n);
iota(all(idx), 0);
}
int update(int _i, int y) {
int i;
for (i = 0; idx[i] != _i; ++i) ;
debug(l);
x[i] = y;
while (i+1 < n && x[i] > x[i+1]) {
swap(x[i], x[i+1]);
swap(idx[i], idx[i+1]);
++i;
}
while (i-1 >= 0 && x[i] < x[i-1]) {
swap(x[i], x[i-1]);
swap(idx[i], idx[i-1]);
--i;
}
debug(x);
int res = 0;
for (int j = 0; j < n; ++j) {
++res;
int k = j;
debug(x[j] + l);
while (k+1 < n && x[j] + l >= x[k+1]) ++k;
debug(j);
debug(k);
j = k;
}
return res;
}
#ifdef LOCAL
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int n, l, m;
cin >> n >> l >> m;
int *x = new int[n];
for (int i = 0; i < n; ++i) cin >> x[i];
init(n, l, x);
for (int i = 0; i < m; ++i) {
int j, y, s;
cin >> j >> y >> s;
int ans = update(j, y);
cout << "ANS = " << ans << ", expected " << s << '\n';
if (ans != s) cout << "WA on query " << i+1 << endl;
}
return 0;
}
#endif
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
440 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
440 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
440 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1365 ms |
2104 KB |
Output is correct |
8 |
Correct |
2474 ms |
2140 KB |
Output is correct |
9 |
Correct |
2926 ms |
3316 KB |
Output is correct |
10 |
Correct |
7273 ms |
3096 KB |
Output is correct |
11 |
Correct |
6654 ms |
3032 KB |
Output is correct |
12 |
Correct |
7591 ms |
3192 KB |
Output is correct |
13 |
Correct |
4946 ms |
2676 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
440 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1365 ms |
2104 KB |
Output is correct |
8 |
Correct |
2474 ms |
2140 KB |
Output is correct |
9 |
Correct |
2926 ms |
3316 KB |
Output is correct |
10 |
Correct |
7273 ms |
3096 KB |
Output is correct |
11 |
Correct |
6654 ms |
3032 KB |
Output is correct |
12 |
Correct |
7591 ms |
3192 KB |
Output is correct |
13 |
Correct |
4946 ms |
2676 KB |
Output is correct |
14 |
Correct |
2161 ms |
2976 KB |
Output is correct |
15 |
Correct |
5349 ms |
2912 KB |
Output is correct |
16 |
Execution timed out |
9049 ms |
3788 KB |
Time limit exceeded |
17 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
440 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1365 ms |
2104 KB |
Output is correct |
8 |
Correct |
2474 ms |
2140 KB |
Output is correct |
9 |
Correct |
2926 ms |
3316 KB |
Output is correct |
10 |
Correct |
7273 ms |
3096 KB |
Output is correct |
11 |
Correct |
6654 ms |
3032 KB |
Output is correct |
12 |
Correct |
7591 ms |
3192 KB |
Output is correct |
13 |
Correct |
4946 ms |
2676 KB |
Output is correct |
14 |
Correct |
2161 ms |
2976 KB |
Output is correct |
15 |
Correct |
5349 ms |
2912 KB |
Output is correct |
16 |
Execution timed out |
9049 ms |
3788 KB |
Time limit exceeded |
17 |
Halted |
0 ms |
0 KB |
- |