oj.uz

Submission #919930

# Submission time Handle Problem Language Result Execution time Memory
919930 2024-02-01T21:12:08 Z Lobo Dancing Elephants (IOI11_elephants) C++17
50 / 100
 9000 ms 34240 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fr first
#define sc second
const int maxn = 7e4+10;
const int lg = 17;
const int B = 187;
#define int long long
int n,s;
set<int> espx;
set<pair<pair<int,int>,int>> pts;
vector<int> x;
int p[maxn][lg+1], d[maxn][lg+1];

void init(int32_t N, int32_t L, int32_t X[])
{
    n = N;
    s = L;
    for(int i = 0; i < n; i++) {
    	pts.insert(mp(mp(X[i],i),0));
    	x.pb(X[i]);
    }
}
int cntq = 0;
int32_t update(int32_t iq, int32_t xq)
{
	if(cntq == 0) {
		vector<pair<pair<int,int>,int>> rem,add;
		for(auto X : pts) {
			if(X.sc == 1) {
				rem.pb(X);
				add.pb(mp(X.fr,0));
			}
		}
		espx.clear();
		for(auto X : rem) pts.erase(X);
		for(auto X : add) pts.insert(X);

		for(int i = 0; i < n; i++) {
			auto it = pts.upper_bound(mp(mp(x[i]+s,n+1),n+1));
			if(it == pts.end()) p[i][0] = -1;
			else {
				p[i][0] = it->fr.sc;
				d[i][0] = x[p[i][0]];
			}
		}

		for(int b = 1; b <= lg; b++) {
			for(int i = 0; i < n; i++) {
				if(p[i][b-1] == -1 or p[p[i][b-1]][b-1] == -1) {
					p[i][b] = -1;
					continue;
				}

				p[i][b] = p[p[i][b-1]][b-1];
				d[i][b] = x[p[i][b]];
			}
		}
	}

	pts.erase(mp(mp(x[iq],iq),0));
	pts.erase(mp(mp(x[iq],iq),1));
	espx.insert(x[iq]);
	// pts.insert(mp(mp(x[iq],iq),-1));
	x[iq] = xq;
	pts.insert(mp(mp(x[iq],iq),1));
	espx.insert(x[iq]);

	int pos = -1;
	int32_t ans = 0;
	while(true) {
		auto it = pts.upper_bound(mp(mp(pos,n+1),n+1));
		if(it == pts.end()) break;
		int i = it->fr.sc;
		pos = x[i];
		auto itfds = espx.lower_bound(pos);
		int nxt;
		if(itfds == espx.end()) nxt = 1e9+10;
		else nxt = *itfds;

		if(it->sc == 0) {
			for(int b = lg; b >= 0; b--) {
				if(p[i][b] != -1 && d[i][b] < nxt) {
					ans+= (1<<b);
					i = p[i][b];
				}
			}
			pos = x[i];
		}
		if(i != -1) {
			pos = pos+s;
			ans+= 1;
		}
	}
	cntq = (cntq+1)%B;
  	return ans;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10584 KB Output is correct
4 Correct 2 ms 10584 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 504 ms 15784 KB Output is correct
8 Correct 648 ms 18140 KB Output is correct
9 Correct 2710 ms 30820 KB Output is correct
10 Correct 2297 ms 30660 KB Output is correct
11 Correct 2466 ms 30924 KB Output is correct
12 Correct 5564 ms 30664 KB Output is correct
13 Correct 2240 ms 30672 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10584 KB Output is correct
4 Correct 2 ms 10584 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 504 ms 15784 KB Output is correct
8 Correct 648 ms 18140 KB Output is correct
9 Correct 2710 ms 30820 KB Output is correct
10 Correct 2297 ms 30660 KB Output is correct
11 Correct 2466 ms 30924 KB Output is correct
12 Correct 5564 ms 30664 KB Output is correct
13 Correct 2240 ms 30672 KB Output is correct
14 Correct 1555 ms 18240 KB Output is correct
15 Correct 1192 ms 20684 KB Output is correct
16 Correct 8052 ms 30668 KB Output is correct
17 Execution timed out 9091 ms 34240 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10584 KB Output is correct
4 Correct 2 ms 10584 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 504 ms 15784 KB Output is correct
8 Correct 648 ms 18140 KB Output is correct
9 Correct 2710 ms 30820 KB Output is correct
10 Correct 2297 ms 30660 KB Output is correct
11 Correct 2466 ms 30924 KB Output is correct
12 Correct 5564 ms 30664 KB Output is correct
13 Correct 2240 ms 30672 KB Output is correct
14 Correct 1555 ms 18240 KB Output is correct
15 Correct 1192 ms 20684 KB Output is correct
16 Correct 8052 ms 30668 KB Output is correct
17 Execution timed out 9091 ms 34240 KB Time limit exceeded
18 Halted 0 ms 0 KB -