oj.uz

답안 #923128

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

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

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

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

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

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