oj.uz

Submission #919931

# Submission time Handle Problem Language Result Execution time Memory
919931 2024-02-01T21:12:39 Z Lobo Dancing Elephants (IOI11_elephants) C++17
97 / 100
 8825 ms 67876 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
#define ll 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 3 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 3 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 10588 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 3 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 10588 KB Output is correct
6 Correct 2 ms 10584 KB Output is correct
7 Correct 452 ms 14424 KB Output is correct
8 Correct 577 ms 14672 KB Output is correct
9 Correct 2336 ms 21384 KB Output is correct
10 Correct 1604 ms 21452 KB Output is correct
11 Correct 1967 ms 20944 KB Output is correct
12 Correct 4480 ms 21304 KB Output is correct
13 Correct 1392 ms 21000 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 10588 KB Output is correct
6 Correct 2 ms 10584 KB Output is correct
7 Correct 452 ms 14424 KB Output is correct
8 Correct 577 ms 14672 KB Output is correct
9 Correct 2336 ms 21384 KB Output is correct
10 Correct 1604 ms 21452 KB Output is correct
11 Correct 1967 ms 20944 KB Output is correct
12 Correct 4480 ms 21304 KB Output is correct
13 Correct 1392 ms 21000 KB Output is correct
14 Correct 1460 ms 15052 KB Output is correct
15 Correct 1079 ms 17484 KB Output is correct
16 Correct 6461 ms 21580 KB Output is correct
17 Correct 8825 ms 21704 KB Output is correct
18 Correct 8612 ms 23500 KB Output is correct
19 Correct 3258 ms 23760 KB Output is correct
20 Correct 8669 ms 23504 KB Output is correct
21 Correct 8506 ms 23500 KB Output is correct
22 Correct 3132 ms 23244 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 10588 KB Output is correct
6 Correct 2 ms 10584 KB Output is correct
7 Correct 452 ms 14424 KB Output is correct
8 Correct 577 ms 14672 KB Output is correct
9 Correct 2336 ms 21384 KB Output is correct
10 Correct 1604 ms 21452 KB Output is correct
11 Correct 1967 ms 20944 KB Output is correct
12 Correct 4480 ms 21304 KB Output is correct
13 Correct 1392 ms 21000 KB Output is correct
14 Correct 1460 ms 15052 KB Output is correct
15 Correct 1079 ms 17484 KB Output is correct
16 Correct 6461 ms 21580 KB Output is correct
17 Correct 8825 ms 21704 KB Output is correct
18 Correct 8612 ms 23500 KB Output is correct
19 Correct 3258 ms 23760 KB Output is correct
20 Correct 8669 ms 23504 KB Output is correct
21 Correct 8506 ms 23500 KB Output is correct
22 Correct 3132 ms 23244 KB Output is correct
23 Runtime error 130 ms 67876 KB Execution killed with signal 11
24 Halted 0 ms 0 KB -