oj.uz

Submission #931361

# Submission time Handle Problem Language Result Execution time Memory
931361 2024-02-21T16:19:16 Z hqminhuwu Dancing Elephants (IOI11_elephants) C++14
100 / 100
 5499 ms 37100 KB 
#include <bits/stdc++.h>
#define forr(_a,_b,_c) for(int _a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <int,int>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"


using namespace std;
const int nn = 5e5 + 5;
const ll oo = 1e9;
const ll mod = 1e9 + 7;
const int uwu = 400;

int nl, n;

struct block {
	vector <pii> v;
	int cnt[2 * uwu + 1], pos[2 * uwu + 1];

	void build (){
		if (v.empty()) return;
		int r = v.size();
		r--;
		cnt[r] = 1, pos[r] = v[r].st;
		ford (l, r, 0){
			while (v[r].st - v[l].st > nl)
				r--;
			if (r == v.size() - 1)
				cnt[l] = 1, pos[l] = v[l].st;
			else cnt[l] = cnt[r + 1] + 1, pos[l] = pos[r + 1];
		}
	}

	void ins (int val, int id){
		v.pb({val, id});
		int i = v.size();
		i--;

		while (i > 0 && v[i] < v[i - 1])
			swap(v[i], v[i - 1]), i--;
	}

	void ers (int id){
		int j;
		forf (i, 0, v.size())
		if (v[i].nd == id)
			j = i;
		forf (i, j, v.size() - 1)
			swap(v[i], v[i + 1]);
		v.pop_back();
	}

	pii get (int u){
		if (u + nl >= v.back().st)
			return {u, 0};
	//	cout << "get " << v.back().st << " " << v.back().nd << "\n";
		int k = upper_bound(all(v), mp(u + nl, 1000000)) - v.begin();
		return {pos[k], cnt[k]};
	}

	void debug (){
		// forf (i, 0, v.size())
		// 	cout <<v[i].st << " " << v[i].nd << " " << cnt[i] << " " << pos[i] << "\n";
	}
};

block b[uwu + 1000];
pii a[nn];
int pos[nn], cnt;

void rs (){
	int j = 0;
	forr (i, 0, uwu)
		for (pii w : b[i].v)
			a[++j] = w;

	// forr (i, 1, n)
	// 	cout << a[i].st << " " << a[i].nd << "\n";
	forr (i, 0, uwu)
		b[i].v.clear();

	forr (i, 1, n)
		b[i / uwu].ins(a[i].st, a[i].nd), pos[a[i].nd] = i / uwu;

	forr (i, 0, uwu)
		b[i].build(), b[i].debug();
}

void debug(){
	forr (i, 0, uwu)
		cout << i << ":\n",b[i].debug();
}

void init (int _n, int _l, int _x[]){
	n = _n;
	nl = _l;
	forr (i, 1, n)
		a[i].st = _x[i - 1], a[i].nd = i;
	sort(a + 1, a + 1 + n);
	rs();
}

int update (int u, int w){

	//cout << L << "\n";
	if (cnt > uwu)
		rs(), cnt = 0;
	cnt++;

	//return 0;

	int j = uwu;

	forr (i, 1, uwu){
		if (b[i].v.empty()) {
			j = i - 1;
			break;
		}

		if (b[i].v[0].st > w){
			j = i - 1;
			break;
		}
	}

	u++;

	b[pos[u]].ers(u);
	b[pos[u]].build();
	b[j].ins(w, u);
	b[j].build();
	pos[u] = j;

	//debug();

	int d = 0, ans = 0;

	forr (i, 0, uwu)
	if (!b[i].v.empty()){
		d = b[i].v[0].st;
		break;
	}
	forr (i, 0, uwu){
		//cout << d <<  " " << ans << "\n";
		if (b[i].v.empty()) continue;
		pii tmp = b[i].get(d);
		d = tmp.st;
		ans += tmp.nd;
	}

	return ans + 1;
}

Compilation message

elephants.cpp: In member function 'void block::build()':
elephants.cpp:39:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |    if (r == v.size() - 1)
      |        ~~^~~~~~~~~~~~~~~
elephants.cpp: In member function 'void block::ers(int)':
elephants.cpp:4:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a)
      |                                              ^
elephants.cpp:56:3: note: in expansion of macro 'forf'
   56 |   forf (i, 0, v.size())
      |   ^~~~
elephants.cpp:4:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a)
      |                                              ^
elephants.cpp:59:3: note: in expansion of macro 'forf'
   59 |   forf (i, j, v.size() - 1)
      |   ^~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:59:9: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |   forf (i, j, v.size() - 1)
      |         ^
elephants.cpp:55:7: note: 'j' was declared here
   55 |   int j;
      |       ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 20824 KB Output is correct
2 Correct 3 ms 20828 KB Output is correct
3 Correct 4 ms 20828 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 20824 KB Output is correct
2 Correct 3 ms 20828 KB Output is correct
3 Correct 4 ms 20828 KB Output is correct
4 Correct 3 ms 20828 KB Output is correct
5 Correct 3 ms 20916 KB Output is correct
6 Correct 3 ms 20828 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 20824 KB Output is correct
2 Correct 3 ms 20828 KB Output is correct
3 Correct 4 ms 20828 KB Output is correct
4 Correct 3 ms 20828 KB Output is correct
5 Correct 3 ms 20916 KB Output is correct
6 Correct 3 ms 20828 KB Output is correct
7 Correct 198 ms 23168 KB Output is correct
8 Correct 221 ms 24248 KB Output is correct
9 Correct 293 ms 27220 KB Output is correct
10 Correct 252 ms 26968 KB Output is correct
11 Correct 231 ms 27008 KB Output is correct
12 Correct 446 ms 27176 KB Output is correct
13 Correct 270 ms 26860 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 20824 KB Output is correct
2 Correct 3 ms 20828 KB Output is correct
3 Correct 4 ms 20828 KB Output is correct
4 Correct 3 ms 20828 KB Output is correct
5 Correct 3 ms 20916 KB Output is correct
6 Correct 3 ms 20828 KB Output is correct
7 Correct 198 ms 23168 KB Output is correct
8 Correct 221 ms 24248 KB Output is correct
9 Correct 293 ms 27220 KB Output is correct
10 Correct 252 ms 26968 KB Output is correct
11 Correct 231 ms 27008 KB Output is correct
12 Correct 446 ms 27176 KB Output is correct
13 Correct 270 ms 26860 KB Output is correct
14 Correct 273 ms 26824 KB Output is correct
15 Correct 355 ms 26788 KB Output is correct
16 Correct 742 ms 29776 KB Output is correct
17 Correct 777 ms 30024 KB Output is correct
18 Correct 835 ms 30036 KB Output is correct
19 Correct 512 ms 30188 KB Output is correct
20 Correct 777 ms 30044 KB Output is correct
21 Correct 745 ms 30032 KB Output is correct
22 Correct 466 ms 29776 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 20824 KB Output is correct
2 Correct 3 ms 20828 KB Output is correct
3 Correct 4 ms 20828 KB Output is correct
4 Correct 3 ms 20828 KB Output is correct
5 Correct 3 ms 20916 KB Output is correct
6 Correct 3 ms 20828 KB Output is correct
7 Correct 198 ms 23168 KB Output is correct
8 Correct 221 ms 24248 KB Output is correct
9 Correct 293 ms 27220 KB Output is correct
10 Correct 252 ms 26968 KB Output is correct
11 Correct 231 ms 27008 KB Output is correct
12 Correct 446 ms 27176 KB Output is correct
13 Correct 270 ms 26860 KB Output is correct
14 Correct 273 ms 26824 KB Output is correct
15 Correct 355 ms 26788 KB Output is correct
16 Correct 742 ms 29776 KB Output is correct
17 Correct 777 ms 30024 KB Output is correct
18 Correct 835 ms 30036 KB Output is correct
19 Correct 512 ms 30188 KB Output is correct
20 Correct 777 ms 30044 KB Output is correct
21 Correct 745 ms 30032 KB Output is correct
22 Correct 466 ms 29776 KB Output is correct
23 Correct 2066 ms 35920 KB Output is correct
24 Correct 2222 ms 35864 KB Output is correct
25 Correct 1719 ms 35924 KB Output is correct
26 Correct 1766 ms 35868 KB Output is correct
27 Correct 1941 ms 35728 KB Output is correct
28 Correct 913 ms 28240 KB Output is correct
29 Correct 880 ms 28240 KB Output is correct
30 Correct 919 ms 28248 KB Output is correct
31 Correct 868 ms 27864 KB Output is correct
32 Correct 1468 ms 35304 KB Output is correct
33 Correct 1297 ms 34636 KB Output is correct
34 Correct 1768 ms 35508 KB Output is correct
35 Correct 1385 ms 35664 KB Output is correct
36 Correct 5499 ms 35280 KB Output is correct
37 Correct 2111 ms 37100 KB Output is correct
38 Correct 1801 ms 34500 KB Output is correct
39 Correct 1745 ms 35664 KB Output is correct
40 Correct 1843 ms 34544 KB Output is correct
41 Correct 2578 ms 35156 KB Output is correct
42 Correct 2687 ms 35532 KB Output is correct