oj.uz

답안 #498849

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
498849 2021-12-26T12:57:28 Z sidon 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
50 / 100
 1466 ms 4928 KB 
#include <bits/stdc++.h>
using namespace std;
#include "elephants.h"
 
const int MAX_N = 150'000, B = 500, INF = 2e9;
 
int N, L, LIM, X[MAX_N], Y[MAX_N], num[MAX_N], pos[MAX_N], inB[MAX_N], q_;
 
vector<int> a[B];
set<pair<int, int>> s;
 
void recalculate(int j) {
	auto &c = a[j];
	int sz = size(c), pt = sz;
 
	for(int i = sz; --i >= 0; ) {
		while(pt && X[c[i]] + L < X[c[pt-1]]) --pt;
 
		num[c[i]] = pt < sz ? num[c[pt]] + 1 : 1;
		pos[c[i]] = pt < sz ? pos[c[pt]] : X[c[i]] + L;
		inB[c[i]] = i;
	}
}
 
void reset() {
	for(int i = 0, j = 0; i < LIM; i++) {
		for(int &v : a[i]) pos[j++] = v;
		a[i].clear();
	}
	for(int i = 0; i < N; i++) {
		Y[pos[i]] = i/B;
		a[i/B].push_back(pos[i]);
	}
	for(int i = 0; i < LIM; i++)
		recalculate(i);
}
 
void init(int n, int l, int x[]) {
	N = n, L = l, LIM = (N - 1)/B + 1;
	for(int i = 0; i < N; i++) {
		X[i] = x[i];
		a[i/B].push_back(i);
		s.insert({X[i], i});
	}
	reset();
}

int update(int i, int y) {
	int l = Y[i], p = inB[i];
	a[l].erase(begin(a[l]) + p);
	recalculate(l);
 
	s.erase (make_pair(X[i], i));
	X[i] = y;
 
 	l = Y[(*--s.upper_bound(make_pair(X[i], N))).second];
	
	s.insert(make_pair(X[i], i));

 	for(p = 0; p < (int)size(a[l]); ++p)
 		if(X[i] <= X[a[l][p]]) break;
	Y[i] = l;
	a[l].insert(begin(a[l]) + p, i);
	recalculate(l);
 
	if(!(++q_ % (B - 2))) reset();
 
	int res = 0, curr = -1;
 
	for(int k = 0; k < LIM; k++) {
		if(empty(a[k]) || curr >= X[a[k].back()]) continue;

 		int j = inB[(*s.upper_bound(make_pair(curr, N))).second];
 
		res += num[a[k][j]];
		curr = pos[a[k][j]];
	}
	return res;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 839 ms 1868 KB Output is correct
8 Correct 896 ms 2232 KB Output is correct
9 Correct 976 ms 4664 KB Output is correct
10 Correct 961 ms 4664 KB Output is correct
11 Correct 991 ms 4664 KB Output is correct
12 Correct 1466 ms 4928 KB Output is correct
13 Correct 1339 ms 4664 KB Output is correct

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 839 ms 1868 KB Output is correct
8 Correct 896 ms 2232 KB Output is correct
9 Correct 976 ms 4664 KB Output is correct
10 Correct 961 ms 4664 KB Output is correct
11 Correct 991 ms 4664 KB Output is correct
12 Correct 1466 ms 4928 KB Output is correct
13 Correct 1339 ms 4664 KB Output is correct
14 Runtime error 194 ms 4776 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 839 ms 1868 KB Output is correct
8 Correct 896 ms 2232 KB Output is correct
9 Correct 976 ms 4664 KB Output is correct
10 Correct 961 ms 4664 KB Output is correct
11 Correct 991 ms 4664 KB Output is correct
12 Correct 1466 ms 4928 KB Output is correct
13 Correct 1339 ms 4664 KB Output is correct
14 Runtime error 194 ms 4776 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -