oj.uz

답안 #919929

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
919929 2024-02-01T21:06:52 Z Lobo 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
50 / 100
 9000 ms 34684 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 = 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -