oj.uz

Submission #1021171

# Submission time Handle Problem Language Result Execution time Memory
1021171 2024-07-12T15:06:00 Z mat_jur Dancing Elephants (IOI11_elephants) C++14
26 / 100
 9000 ms 2780 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#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

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 452 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1214 ms 2100 KB Output is correct
8 Correct 2252 ms 2008 KB Output is correct
9 Correct 2929 ms 2780 KB Output is correct
10 Execution timed out 9064 ms 2768 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 452 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1214 ms 2100 KB Output is correct
8 Correct 2252 ms 2008 KB Output is correct
9 Correct 2929 ms 2780 KB Output is correct
10 Execution timed out 9064 ms 2768 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 452 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1214 ms 2100 KB Output is correct
8 Correct 2252 ms 2008 KB Output is correct
9 Correct 2929 ms 2780 KB Output is correct
10 Execution timed out 9064 ms 2768 KB Time limit exceeded
11 Halted 0 ms 0 KB -