oj.uz

Submission #923127

# Submission time Handle Problem Language Result Execution time Memory
923127 2024-02-06T17:35:24 Z Lobo Dancing Elephants (IOI11_elephants) C++17
50 / 100
 9000 ms 23580 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
#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 {
	// 		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;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 10584 KB Output is correct
3 Correct 1 ms 10752 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 1 ms 10584 KB Output is correct
3 Correct 1 ms 10752 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10692 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 1 ms 10584 KB Output is correct
3 Correct 1 ms 10752 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10692 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 989 ms 14660 KB Output is correct
8 Correct 1077 ms 15036 KB Output is correct
9 Correct 2142 ms 21904 KB Output is correct
10 Correct 1714 ms 21500 KB Output is correct
11 Correct 1915 ms 21460 KB Output is correct
12 Correct 5134 ms 21704 KB Output is correct
13 Correct 1600 ms 21396 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 1 ms 10584 KB Output is correct
3 Correct 1 ms 10752 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10692 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 989 ms 14660 KB Output is correct
8 Correct 1077 ms 15036 KB Output is correct
9 Correct 2142 ms 21904 KB Output is correct
10 Correct 1714 ms 21500 KB Output is correct
11 Correct 1915 ms 21460 KB Output is correct
12 Correct 5134 ms 21704 KB Output is correct
13 Correct 1600 ms 21396 KB Output is correct
14 Correct 1797 ms 15528 KB Output is correct
15 Correct 1397 ms 17852 KB Output is correct
16 Correct 7483 ms 21972 KB Output is correct
17 Execution timed out 9038 ms 23580 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 1 ms 10584 KB Output is correct
3 Correct 1 ms 10752 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10692 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 989 ms 14660 KB Output is correct
8 Correct 1077 ms 15036 KB Output is correct
9 Correct 2142 ms 21904 KB Output is correct
10 Correct 1714 ms 21500 KB Output is correct
11 Correct 1915 ms 21460 KB Output is correct
12 Correct 5134 ms 21704 KB Output is correct
13 Correct 1600 ms 21396 KB Output is correct
14 Correct 1797 ms 15528 KB Output is correct
15 Correct 1397 ms 17852 KB Output is correct
16 Correct 7483 ms 21972 KB Output is correct
17 Execution timed out 9038 ms 23580 KB Time limit exceeded
18 Halted 0 ms 0 KB -