답안 #62194 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
62194	2018-07-27T19:18:46 Z	reality	코끼리 (Dancing Elephants) (IOI11_elephants)	C++17	97 / 100	9000 ms	85212 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;

int K;

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;
	K = sqrt(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:126: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	67 ms	70776 KB	Output is correct
2	Correct	75 ms	70904 KB	Output is correct
3	Correct	73 ms	70904 KB	Output is correct

Subtask #2
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	67 ms	70776 KB	Output is correct
2	Correct	75 ms	70904 KB	Output is correct
3	Correct	73 ms	70904 KB	Output is correct
4	Correct	68 ms	71088 KB	Output is correct
5	Correct	74 ms	71088 KB	Output is correct
6	Correct	73 ms	71088 KB	Output is correct

Subtask #3
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	67 ms	70776 KB	Output is correct
2	Correct	75 ms	70904 KB	Output is correct
3	Correct	73 ms	70904 KB	Output is correct
4	Correct	68 ms	71088 KB	Output is correct
5	Correct	74 ms	71088 KB	Output is correct
6	Correct	73 ms	71088 KB	Output is correct
7	Correct	536 ms	72716 KB	Output is correct
8	Correct	652 ms	73172 KB	Output is correct
9	Correct	1004 ms	75440 KB	Output is correct
10	Correct	831 ms	75440 KB	Output is correct
11	Correct	991 ms	75440 KB	Output is correct
12	Correct	1421 ms	75652 KB	Output is correct
13	Correct	849 ms	75652 KB	Output is correct

Subtask #4
47.0 / 47.0

#	결과	실행 시간	메모리	Grader output
1	Correct	67 ms	70776 KB	Output is correct
2	Correct	75 ms	70904 KB	Output is correct
3	Correct	73 ms	70904 KB	Output is correct
4	Correct	68 ms	71088 KB	Output is correct
5	Correct	74 ms	71088 KB	Output is correct
6	Correct	73 ms	71088 KB	Output is correct
7	Correct	536 ms	72716 KB	Output is correct
8	Correct	652 ms	73172 KB	Output is correct
9	Correct	1004 ms	75440 KB	Output is correct
10	Correct	831 ms	75440 KB	Output is correct
11	Correct	991 ms	75440 KB	Output is correct
12	Correct	1421 ms	75652 KB	Output is correct
13	Correct	849 ms	75652 KB	Output is correct
14	Correct	956 ms	75652 KB	Output is correct
15	Correct	1173 ms	75652 KB	Output is correct
16	Correct	2706 ms	75844 KB	Output is correct
17	Correct	2906 ms	77644 KB	Output is correct
18	Correct	3468 ms	77644 KB	Output is correct
19	Correct	1801 ms	77644 KB	Output is correct
20	Correct	3239 ms	77644 KB	Output is correct
21	Correct	3192 ms	77644 KB	Output is correct
22	Correct	1638 ms	77644 KB	Output is correct

Subtask #5
0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	67 ms	70776 KB	Output is correct
2	Correct	75 ms	70904 KB	Output is correct
3	Correct	73 ms	70904 KB	Output is correct
4	Correct	68 ms	71088 KB	Output is correct
5	Correct	74 ms	71088 KB	Output is correct
6	Correct	73 ms	71088 KB	Output is correct
7	Correct	536 ms	72716 KB	Output is correct
8	Correct	652 ms	73172 KB	Output is correct
9	Correct	1004 ms	75440 KB	Output is correct
10	Correct	831 ms	75440 KB	Output is correct
11	Correct	991 ms	75440 KB	Output is correct
12	Correct	1421 ms	75652 KB	Output is correct
13	Correct	849 ms	75652 KB	Output is correct
14	Correct	956 ms	75652 KB	Output is correct
15	Correct	1173 ms	75652 KB	Output is correct
16	Correct	2706 ms	75844 KB	Output is correct
17	Correct	2906 ms	77644 KB	Output is correct
18	Correct	3468 ms	77644 KB	Output is correct
19	Correct	1801 ms	77644 KB	Output is correct
20	Correct	3239 ms	77644 KB	Output is correct
21	Correct	3192 ms	77644 KB	Output is correct
22	Correct	1638 ms	77644 KB	Output is correct
23	Correct	5875 ms	83856 KB	Output is correct
24	Correct	6500 ms	84072 KB	Output is correct
25	Correct	5782 ms	84072 KB	Output is correct
26	Correct	6170 ms	84072 KB	Output is correct
27	Correct	6130 ms	84072 KB	Output is correct
28	Correct	1071 ms	84072 KB	Output is correct
29	Correct	1040 ms	84072 KB	Output is correct
30	Correct	1268 ms	84072 KB	Output is correct
31	Correct	1316 ms	84072 KB	Output is correct
32	Correct	5880 ms	84072 KB	Output is correct
33	Correct	5334 ms	84072 KB	Output is correct
34	Correct	5331 ms	84072 KB	Output is correct
35	Correct	5794 ms	85212 KB	Output is correct
36	Correct	4530 ms	85212 KB	Output is correct
37	Execution timed out	9059 ms	85212 KB	Time limit exceeded
38	Halted	0 ms	0 KB	-

답안 #62194

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 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
0 / 3.0