oj.uz

Submission #787058

# Submission time Handle Problem Language Result Execution time Memory
787058 2023-07-18T17:45:41 Z Cyber_Wolf Dancing Elephants (IOI11_elephants) C++11
50 / 100
 9000 ms 3536 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 308 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 308 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1024 ms 1956 KB Output is correct
8 Correct 2037 ms 2124 KB Output is correct
9 Correct 1410 ms 3048 KB Output is correct
10 Correct 3143 ms 2828 KB Output is correct
11 Correct 3193 ms 2764 KB Output is correct
12 Correct 6305 ms 2920 KB Output is correct
13 Correct 3356 ms 2620 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 308 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1024 ms 1956 KB Output is correct
8 Correct 2037 ms 2124 KB Output is correct
9 Correct 1410 ms 3048 KB Output is correct
10 Correct 3143 ms 2828 KB Output is correct
11 Correct 3193 ms 2764 KB Output is correct
12 Correct 6305 ms 2920 KB Output is correct
13 Correct 3356 ms 2620 KB Output is correct
14 Correct 1268 ms 2844 KB Output is correct
15 Correct 4455 ms 2820 KB Output is correct
16 Execution timed out 9066 ms 3536 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 308 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1024 ms 1956 KB Output is correct
8 Correct 2037 ms 2124 KB Output is correct
9 Correct 1410 ms 3048 KB Output is correct
10 Correct 3143 ms 2828 KB Output is correct
11 Correct 3193 ms 2764 KB Output is correct
12 Correct 6305 ms 2920 KB Output is correct
13 Correct 3356 ms 2620 KB Output is correct
14 Correct 1268 ms 2844 KB Output is correct
15 Correct 4455 ms 2820 KB Output is correct
16 Execution timed out 9066 ms 3536 KB Time limit exceeded
17 Halted 0 ms 0 KB -