Submission #919929

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
919929	2024-02-01T21:06:52 Z	Lobo	Dancing Elephants (IOI11_elephants)	C++17	50 / 100	9000 ms	34684 KB

elephants

#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 = 20;
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]];
				// auto it = pts.upper_bound(mp(mp(d[i][b-1],n+1),n+1));
				// if(it == pts.end()) {
				// 	d[i][b] = -1;
				// }
				// else {
				// 	d[i][b] = d[it->fr.sc][b-1];
				// }
			}
		}
	}

	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;

		// cout << i << " " << pos << " " << nxt << " " << ans << endl;

		if(it->sc == 0) {
			for(int b = lg; b >= 1; b--) {
				if(p[i][b] == -1) continue;
				// it = pts.upper_bound(mp(mp(d[i][b],n+1),n+1));
				// cout << " " << i << " " << b << " " << d[i][b] << " " << nxt << " " << ans << endl;
				
				if(d[i][b] < nxt) {
					ans+= (1<<b);
					i = p[i][b];
					pos = x[i];

					// it = pts.upper_bound(mp(mp(pos,n+1),n+1));
					// if(it == pts.end() or it->fr.fr >= nxt) {
					// 	i = -1;
					// 	break;
					// }
					// i = it->fr.sc;
					// 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	10584 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	10584 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	10584 KB	Output is correct
6	Correct	2 ms	10584 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	10584 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	10584 KB	Output is correct
6	Correct	2 ms	10584 KB	Output is correct
7	Correct	517 ms	17832 KB	Output is correct
8	Correct	678 ms	20288 KB	Output is correct
9	Correct	3451 ms	32872 KB	Output is correct
10	Correct	2818 ms	34212 KB	Output is correct
11	Correct	3040 ms	33996 KB	Output is correct
12	Correct	6816 ms	34248 KB	Output is correct
13	Correct	2637 ms	33996 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	10584 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	10584 KB	Output is correct
6	Correct	2 ms	10584 KB	Output is correct
7	Correct	517 ms	17832 KB	Output is correct
8	Correct	678 ms	20288 KB	Output is correct
9	Correct	3451 ms	32872 KB	Output is correct
10	Correct	2818 ms	34212 KB	Output is correct
11	Correct	3040 ms	33996 KB	Output is correct
12	Correct	6816 ms	34248 KB	Output is correct
13	Correct	2637 ms	33996 KB	Output is correct
14	Correct	1865 ms	21712 KB	Output is correct
15	Correct	1279 ms	24088 KB	Output is correct
16	Execution timed out	9101 ms	34684 KB	Time limit exceeded
17	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	10584 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	10584 KB	Output is correct
6	Correct	2 ms	10584 KB	Output is correct
7	Correct	517 ms	17832 KB	Output is correct
8	Correct	678 ms	20288 KB	Output is correct
9	Correct	3451 ms	32872 KB	Output is correct
10	Correct	2818 ms	34212 KB	Output is correct
11	Correct	3040 ms	33996 KB	Output is correct
12	Correct	6816 ms	34248 KB	Output is correct
13	Correct	2637 ms	33996 KB	Output is correct
14	Correct	1865 ms	21712 KB	Output is correct
15	Correct	1279 ms	24088 KB	Output is correct
16	Execution timed out	9101 ms	34684 KB	Time limit exceeded
17	Halted	0 ms	0 KB	-