oj.uz

Submission #414761

# Submission time Handle Problem Language Result Execution time Memory
414761 2021-05-31T07:18:46 Z jeqcho Dancing Elephants (IOI11_elephants) C++17
26 / 100
 9000 ms 5584 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pair<int,int>> vpi;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define rsz resize
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define fi first
#define se second

int N;
int L;
int const n=5e4+3;
int pre[n];
int nxt[n];
int X[n];
set<pii>st;
int mn;
int const INF=2e9;
// subtask 1,2

void init(int N1, int L1, int X1[])
{
	L=L1;
	N = N1;
	F0R(i,N)
	{
		X[i]=X1[i];
		st.insert({X[i],i});
	}
	st.insert({INF,N});
	int prev=-1;
	mn=(*st.begin()).se;
	trav(e,st)
	{
		pre[e.se]=prev;
		if(prev!=-1)nxt[prev]=e.se;
		prev=e.se;
	}
	nxt[(*st.rbegin()).se]=N;
}

int update(int idx, int y)
{
	int prev = pre[idx];
	int next = nxt[idx];
	pre[next]=prev;
	if(prev!=-1)nxt[prev]=next;
	else mn=next;
	st.erase({X[idx],idx});
	next = (*st.upper_bound({y,-1})).se;
	prev = pre[next];
	nxt[idx] = next;
	pre[idx] = prev;
	if(prev!=-1)nxt[prev] = idx;
	else mn=idx;
	pre[next] = idx;
	X[idx]=y;
	st.insert({y,idx});
	int cnt=0;
	int b=-1;
	int cur=mn;
	while(cur!=N)
	{
		if(X[cur]>b)
		{
			++cnt;
			b = X[cur]+L;
		}
		cur=nxt[cur];
	}
	return cnt;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2863 ms 2584 KB Output is correct
8 Correct 4154 ms 3008 KB Output is correct
9 Correct 5963 ms 5584 KB Output is correct
10 Correct 6285 ms 5368 KB Output is correct
11 Correct 6093 ms 5296 KB Output is correct
12 Execution timed out 9021 ms 5400 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2863 ms 2584 KB Output is correct
8 Correct 4154 ms 3008 KB Output is correct
9 Correct 5963 ms 5584 KB Output is correct
10 Correct 6285 ms 5368 KB Output is correct
11 Correct 6093 ms 5296 KB Output is correct
12 Execution timed out 9021 ms 5400 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2863 ms 2584 KB Output is correct
8 Correct 4154 ms 3008 KB Output is correct
9 Correct 5963 ms 5584 KB Output is correct
10 Correct 6285 ms 5368 KB Output is correct
11 Correct 6093 ms 5296 KB Output is correct
12 Execution timed out 9021 ms 5400 KB Time limit exceeded
13 Halted 0 ms 0 KB -