Submission #923128

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
923128	2024-02-06T17:36:45 Z	Lobo	Dancing Elephants (IOI11_elephants)	C++17	50 / 100	9000 ms	21452 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
#define all(x) x.begin(),x.end()
const int maxn = 7e4+10;
const int lg = 17;
const int B = 187;
// #define int long long
#define ll long long
int n,s;
vector<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;

void putespx(int val) {
	int sub = -1;
	for(int i = 0; i < espx.size(); i++) {
		if(espx[i] == val) return;
		if(sub == -1 && espx[i] > val) {
			sub = val;
			swap(espx[i],sub);
		}
		else if(sub != -1) {
			swap(espx[i],sub);
		}
	}
	if(sub == -1) sub = val;
	espx.pb(sub);

	// espx.pb(val);
	// sort(all(espx));
	// espx.erase(unique(all(espx)),espx.end());
}
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]);
	putespx(x[iq]);
	x[iq] = xq;
	pts.insert(mp(mp(x[iq],iq),1));
	// espx.insert(x[iq]);
	putespx(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 = lower_bound(all(espx),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;
}

Compilation message

elephants.cpp: In function 'void putespx(int)':
elephants.cpp:33:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for(int i = 0; i < espx.size(); i++) {
      |                 ~~^~~~~~~~~~~~~

Subtask #1

10.0 / 10.0

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

Subtask #2

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	10588 KB	Output is correct
2	Correct	2 ms	10588 KB	Output is correct
3	Correct	1 ms	10588 KB	Output is correct
4	Correct	2 ms	10588 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	1 ms	10588 KB	Output is correct
2	Correct	2 ms	10588 KB	Output is correct
3	Correct	1 ms	10588 KB	Output is correct
4	Correct	2 ms	10588 KB	Output is correct
5	Correct	2 ms	10588 KB	Output is correct
6	Correct	2 ms	10588 KB	Output is correct
7	Correct	548 ms	13660 KB	Output is correct
8	Correct	686 ms	14028 KB	Output is correct
9	Correct	2073 ms	20352 KB	Output is correct
10	Correct	1483 ms	20172 KB	Output is correct
11	Correct	1723 ms	20172 KB	Output is correct
12	Correct	4843 ms	20172 KB	Output is correct
13	Correct	1482 ms	20292 KB	Output is correct

Subtask #4

0 / 47.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	10588 KB	Output is correct
2	Correct	2 ms	10588 KB	Output is correct
3	Correct	1 ms	10588 KB	Output is correct
4	Correct	2 ms	10588 KB	Output is correct
5	Correct	2 ms	10588 KB	Output is correct
6	Correct	2 ms	10588 KB	Output is correct
7	Correct	548 ms	13660 KB	Output is correct
8	Correct	686 ms	14028 KB	Output is correct
9	Correct	2073 ms	20352 KB	Output is correct
10	Correct	1483 ms	20172 KB	Output is correct
11	Correct	1723 ms	20172 KB	Output is correct
12	Correct	4843 ms	20172 KB	Output is correct
13	Correct	1482 ms	20292 KB	Output is correct
14	Correct	1650 ms	14092 KB	Output is correct
15	Correct	1267 ms	16476 KB	Output is correct
16	Correct	6945 ms	20280 KB	Output is correct
17	Execution timed out	9031 ms	21452 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-

Subtask #5

0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	10588 KB	Output is correct
2	Correct	2 ms	10588 KB	Output is correct
3	Correct	1 ms	10588 KB	Output is correct
4	Correct	2 ms	10588 KB	Output is correct
5	Correct	2 ms	10588 KB	Output is correct
6	Correct	2 ms	10588 KB	Output is correct
7	Correct	548 ms	13660 KB	Output is correct
8	Correct	686 ms	14028 KB	Output is correct
9	Correct	2073 ms	20352 KB	Output is correct
10	Correct	1483 ms	20172 KB	Output is correct
11	Correct	1723 ms	20172 KB	Output is correct
12	Correct	4843 ms	20172 KB	Output is correct
13	Correct	1482 ms	20292 KB	Output is correct
14	Correct	1650 ms	14092 KB	Output is correct
15	Correct	1267 ms	16476 KB	Output is correct
16	Correct	6945 ms	20280 KB	Output is correct
17	Execution timed out	9031 ms	21452 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-