oj.uz

답안 #529381

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
529381 2022-02-22T22:58:11 Z flappybird 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
26 / 100
 9000 ms 18508 KB 
#include "elephants.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
#define MAX 150010
#define B 100

int N;
int L;
int arr[MAX];
int cnt;
map<int, int> ncnt;
int gcnt;
set<int> allv;
set<pair<int, pi>> bukkit[MAX];

//refresh bukkit
void refb(int b) {
	if (bukkit[b].empty()) return;
	set<pair<int, pi>> s1;
	for (auto it = prev(bukkit[b].end());; it--) {
		int x = it->first;
		int e = x + L;
		auto ub = s1.lower_bound(make_pair(e + 1, pi(0, 0)));
		pair<int, pi> ins;
		ins.first = x;
		if (ub == s1.end()) ins.second = pi(1, e);
		else ins.second = pi(ub->second.first + 1, ub->second.second);
		s1.insert(ins);
		if (it == bukkit[b].begin()) break;
	}
	bukkit[b].swap(s1);
}

void ref() {
	for (int i = 0; i < gcnt; i++) bukkit[i].clear();
	gcnt = 0;
	for (auto v : allv) {
		if (bukkit[gcnt].size() == B) gcnt++;
		bukkit[gcnt].insert(make_pair(v, pi(0, 0)));
	}
	gcnt++;
	for (int i = 0; i < gcnt; i++) refb(i);
}

int calc() {
	int en = -2, i;
	int cnt = 0;
	for (i = 0; i < gcnt; i++) {
		if (bukkit[i].empty()) continue;
		auto ub = bukkit[i].lower_bound(make_pair(en + 1, pi(0, 0)));
		if (ub == bukkit[i].end()) continue;
		cnt += ub->second.first;
		en = ub->second.second;
	}
	return cnt;
}

void init(int N, int L, int X[]) {
	::N = N;
	::L = L;
	int i;
	for (i = 0; i < N; i++) arr[i] = X[i], allv.insert(arr[i]), ncnt[arr[i]]++;
	ref();
}

int update(int i, int y) {
	cnt++;
	if (cnt == B) ref(), cnt = 0;
	int x = arr[i];
	arr[i] = y;
	ncnt[x]--;
	if (ncnt[x] == 0) {
		int i, ind = 0;
		for (i = 0; i < gcnt; i++) if (bukkit[i].size() && bukkit[i].begin()->first <= x) ind = i;
		auto it = bukkit[ind].lower_bound(make_pair(x, pi(0, 0)));
		bukkit[ind].erase(it);
		allv.erase(x);
		refb(ind);
	}
	if (ncnt[y] == 0) {
		allv.insert(y);
		int i, ind = 0;
		for (i = 0; i < gcnt; i++) if (bukkit[i].size() && bukkit[i].begin()->first <= y) ind = i;
		bukkit[ind].insert(make_pair(y, pi(0, 0)));
		allv.insert(y);
		refb(ind);
	}
	ncnt[y]++;
	return calc();
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 7372 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 7372 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 6 ms 7404 KB Output is correct
5 Correct 6 ms 7372 KB Output is correct
6 Correct 4 ms 7372 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 7372 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 6 ms 7404 KB Output is correct
5 Correct 6 ms 7372 KB Output is correct
6 Correct 4 ms 7372 KB Output is correct
7 Correct 2416 ms 12132 KB Output is correct
8 Correct 2960 ms 12980 KB Output is correct
9 Correct 8492 ms 17080 KB Output is correct
10 Correct 6435 ms 18476 KB Output is correct
11 Correct 6064 ms 18508 KB Output is correct
12 Execution timed out 9085 ms 18500 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 7372 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 6 ms 7404 KB Output is correct
5 Correct 6 ms 7372 KB Output is correct
6 Correct 4 ms 7372 KB Output is correct
7 Correct 2416 ms 12132 KB Output is correct
8 Correct 2960 ms 12980 KB Output is correct
9 Correct 8492 ms 17080 KB Output is correct
10 Correct 6435 ms 18476 KB Output is correct
11 Correct 6064 ms 18508 KB Output is correct
12 Execution timed out 9085 ms 18500 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 7372 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 6 ms 7404 KB Output is correct
5 Correct 6 ms 7372 KB Output is correct
6 Correct 4 ms 7372 KB Output is correct
7 Correct 2416 ms 12132 KB Output is correct
8 Correct 2960 ms 12980 KB Output is correct
9 Correct 8492 ms 17080 KB Output is correct
10 Correct 6435 ms 18476 KB Output is correct
11 Correct 6064 ms 18508 KB Output is correct
12 Execution timed out 9085 ms 18500 KB Time limit exceeded
13 Halted 0 ms 0 KB -