답안 #62197 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
62197	2018-07-27T19:30:19 Z	reality	코끼리 (Dancing Elephants) (IOI11_elephants)	C++17	100 / 100	8637 ms	85448 KB

elephants

#include "elephants.h"
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}

int n,l;
vi s;

const int K = 1000;

const int oo = 2e9 + 5;

const int NN = 1e6 + 5;

int Step = 0;

multiset < int > ss;

vi v[NN];

vi dp1[NN];

vi dp2[NN];

int SZ;

void build_block(int w) {
	int sz = v[w].size();
	int index = sz;
	dp1[w].resize(sz);
	dp2[w].resize(sz);
	for (int j = sz - 1;j >= 0;--j) {
		while (v[w][j] + l < v[w][index - 1])
			--index;
		dp1[w][j] = 1;
		dp2[w][j] = v[w][j];
		if (index < sz)
			dp1[w][j] += dp1[w][index],dp2[w][j] = dp2[w][index];
	}
}

void del(int val) {
	for (int i = 0;i < SZ;++i) 
		if (!v[i].empty() && v[i][0] <= val && val <= v[i].back()) {
			vi nw;
			for (auto it : v[i])
				if (it != val)
					nw.pb(it);
				else
					val = oo;
			assert(nw.size() + 1 == v[i].size());
			v[i] = nw;
			build_block(i);
			break;
		}
}

void add(int val) {
	int pr = SZ - 1;
	for (int i = 0;i < SZ;++i) 
		if (!v[i].empty() && val <= v[i].back()) {
			pr = i;
			break;
		}
	vi nw;
	for (auto it : v[pr]) {
		if (it > val)
			nw.pb(val),val = oo;
		nw.pb(it);
	}
	if (val != oo)
		nw.pb(val);
	v[pr] = nw;
	build_block(pr);
}

void build(void) {
	int index = -1;
	SZ = (ss.size() + K - 1) / K;
	for (int i = 0;i < SZ;++i)
		v[i].clear(),dp1[i].clear(),dp2[i].clear();
	for (auto it : ss) {
		++index;
		v[index / K].pb(it);
	}
	for (int i = 0;i < SZ;++i) {
		build_block(i);
	}
}

void init(int N, int L, int X[]) {
	n = N;
	l = L;
	for (int i = 0;i < n;++i)
		s.pb(X[i]),ss.insert(X[i]);
}

int update(int i, int y) {
	if (!(Step % K)) {
		build();
	}
	++Step;
	ss.erase(ss.find(s[i]));
	del(s[i]);
	ss.insert(y);
	add(s[i] = y);
	int prev = -oo;
	int ans = 0;
	for (int i = 0;i < SZ;++i) {
		if (v[i].empty())
			continue;
		int low = lower_bound(all(v[i]),prev) - v[i].begin();
		if (low != v[i].size()) {
			ans += dp1[i][low];
			prev = dp2[i][low] + l + 1;
		}
	}
	return ans;
}

Compilation message

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:125:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (low != v[i].size()) {
       ~~~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	75 ms	70776 KB	Output is correct
2	Correct	75 ms	70776 KB	Output is correct
3	Correct	84 ms	70792 KB	Output is correct

Subtask #2
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	75 ms	70776 KB	Output is correct
2	Correct	75 ms	70776 KB	Output is correct
3	Correct	84 ms	70792 KB	Output is correct
4	Correct	75 ms	70920 KB	Output is correct
5	Correct	82 ms	70984 KB	Output is correct
6	Correct	86 ms	71072 KB	Output is correct

Subtask #3
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	75 ms	70776 KB	Output is correct
2	Correct	75 ms	70776 KB	Output is correct
3	Correct	84 ms	70792 KB	Output is correct
4	Correct	75 ms	70920 KB	Output is correct
5	Correct	82 ms	70984 KB	Output is correct
6	Correct	86 ms	71072 KB	Output is correct
7	Correct	1226 ms	72680 KB	Output is correct
8	Correct	1317 ms	73140 KB	Output is correct
9	Correct	1429 ms	75220 KB	Output is correct
10	Correct	1466 ms	75220 KB	Output is correct
11	Correct	1296 ms	75220 KB	Output is correct
12	Correct	1933 ms	75456 KB	Output is correct
13	Correct	1251 ms	75456 KB	Output is correct

Subtask #4
47.0 / 47.0

#	결과	실행 시간	메모리	Grader output
1	Correct	75 ms	70776 KB	Output is correct
2	Correct	75 ms	70776 KB	Output is correct
3	Correct	84 ms	70792 KB	Output is correct
4	Correct	75 ms	70920 KB	Output is correct
5	Correct	82 ms	70984 KB	Output is correct
6	Correct	86 ms	71072 KB	Output is correct
7	Correct	1226 ms	72680 KB	Output is correct
8	Correct	1317 ms	73140 KB	Output is correct
9	Correct	1429 ms	75220 KB	Output is correct
10	Correct	1466 ms	75220 KB	Output is correct
11	Correct	1296 ms	75220 KB	Output is correct
12	Correct	1933 ms	75456 KB	Output is correct
13	Correct	1251 ms	75456 KB	Output is correct
14	Correct	1365 ms	75456 KB	Output is correct
15	Correct	1493 ms	75456 KB	Output is correct
16	Correct	2845 ms	75584 KB	Output is correct
17	Correct	3059 ms	77264 KB	Output is correct
18	Correct	3195 ms	77264 KB	Output is correct
19	Correct	1741 ms	77264 KB	Output is correct
20	Correct	2845 ms	77264 KB	Output is correct
21	Correct	2715 ms	77264 KB	Output is correct
22	Correct	1878 ms	77264 KB	Output is correct

Subtask #5
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	75 ms	70776 KB	Output is correct
2	Correct	75 ms	70776 KB	Output is correct
3	Correct	84 ms	70792 KB	Output is correct
4	Correct	75 ms	70920 KB	Output is correct
5	Correct	82 ms	70984 KB	Output is correct
6	Correct	86 ms	71072 KB	Output is correct
7	Correct	1226 ms	72680 KB	Output is correct
8	Correct	1317 ms	73140 KB	Output is correct
9	Correct	1429 ms	75220 KB	Output is correct
10	Correct	1466 ms	75220 KB	Output is correct
11	Correct	1296 ms	75220 KB	Output is correct
12	Correct	1933 ms	75456 KB	Output is correct
13	Correct	1251 ms	75456 KB	Output is correct
14	Correct	1365 ms	75456 KB	Output is correct
15	Correct	1493 ms	75456 KB	Output is correct
16	Correct	2845 ms	75584 KB	Output is correct
17	Correct	3059 ms	77264 KB	Output is correct
18	Correct	3195 ms	77264 KB	Output is correct
19	Correct	1741 ms	77264 KB	Output is correct
20	Correct	2845 ms	77264 KB	Output is correct
21	Correct	2715 ms	77264 KB	Output is correct
22	Correct	1878 ms	77264 KB	Output is correct
23	Correct	5830 ms	83720 KB	Output is correct
24	Correct	5825 ms	83904 KB	Output is correct
25	Correct	4625 ms	83904 KB	Output is correct
26	Correct	4965 ms	83904 KB	Output is correct
27	Correct	5121 ms	83904 KB	Output is correct
28	Correct	4735 ms	83904 KB	Output is correct
29	Correct	4998 ms	83904 KB	Output is correct
30	Correct	4654 ms	83904 KB	Output is correct
31	Correct	5055 ms	83904 KB	Output is correct
32	Correct	4664 ms	83904 KB	Output is correct
33	Correct	4465 ms	83904 KB	Output is correct
34	Correct	4632 ms	83904 KB	Output is correct
35	Correct	4781 ms	85448 KB	Output is correct
36	Correct	4279 ms	85448 KB	Output is correct
37	Correct	7427 ms	85448 KB	Output is correct
38	Correct	4476 ms	85448 KB	Output is correct
39	Correct	5016 ms	85448 KB	Output is correct
40	Correct	4580 ms	85448 KB	Output is correct
41	Correct	8189 ms	85448 KB	Output is correct
42	Correct	8637 ms	85448 KB	Output is correct

답안 #62197

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 16.0 / 16.0

Subtask #3 24.0 / 24.0

Subtask #4 47.0 / 47.0

Subtask #5 3.0 / 3.0

Subtask #1
10.0 / 10.0

Subtask #2
16.0 / 16.0

Subtask #3
24.0 / 24.0

Subtask #4
47.0 / 47.0

Subtask #5
3.0 / 3.0