oj.uz

Submission #785985

# Submission time Handle Problem Language Result Execution time Memory
785985 2023-07-17T21:20:48 Z Cyber_Wolf Dancing Elephants (IOI11_elephants) C++17
50 / 100
 9000 ms 3404 KB 
// Problem: P5 - Dancing Elephants
// Contest: DMOJ - IOI '11
// URL: https://dmoj.ca/problem/ioi11p5
// Memory Limit: 256 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

using namespace std;

int n, l;
int x[150000], o[150000];
// int idx[150000];

void init(int N, int L, int X[])
{
	n = N, l = L;
	for(int i = 0; i < N; i++)
	{
		x[i] = X[i];	
		o[i] = x[i];
	}
	return;
}

int update(int i, int y)
{
	int p = lower_bound(x, x+n, o[i])-x;
	x[p] = y;
	o[i] = y;
	while(p && x[p] < x[p-1])	
	{
		swap(x[p], x[p-1]);
		p--;
	}
	while(p+1 < n && x[p] > x[p+1])
	{
		swap(x[p], x[p+1]);
		p++;
	}
	int beg = x[0];
	int ans = 1;
	for(int j = 0; j < n; j++)
	{
		if(x[j]-beg > l)
		{
			beg = x[j];
			ans++;
		}
	}
	return ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1089 ms 1976 KB Output is correct
8 Correct 1995 ms 2116 KB Output is correct
9 Correct 1462 ms 3048 KB Output is correct
10 Correct 3308 ms 2828 KB Output is correct
11 Correct 3132 ms 2768 KB Output is correct
12 Correct 6401 ms 2924 KB Output is correct
13 Correct 3369 ms 2552 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1089 ms 1976 KB Output is correct
8 Correct 1995 ms 2116 KB Output is correct
9 Correct 1462 ms 3048 KB Output is correct
10 Correct 3308 ms 2828 KB Output is correct
11 Correct 3132 ms 2768 KB Output is correct
12 Correct 6401 ms 2924 KB Output is correct
13 Correct 3369 ms 2552 KB Output is correct
14 Correct 1295 ms 2848 KB Output is correct
15 Correct 4387 ms 2828 KB Output is correct
16 Execution timed out 9044 ms 3404 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1089 ms 1976 KB Output is correct
8 Correct 1995 ms 2116 KB Output is correct
9 Correct 1462 ms 3048 KB Output is correct
10 Correct 3308 ms 2828 KB Output is correct
11 Correct 3132 ms 2768 KB Output is correct
12 Correct 6401 ms 2924 KB Output is correct
13 Correct 3369 ms 2552 KB Output is correct
14 Correct 1295 ms 2848 KB Output is correct
15 Correct 4387 ms 2828 KB Output is correct
16 Execution timed out 9044 ms 3404 KB Time limit exceeded
17 Halted 0 ms 0 KB -