oj.uz

Submission #931356

# Submission time Handle Problem Language Result Execution time Memory
931356 2024-02-21T16:10:10 Z hqminhuwu Dancing Elephants (IOI11_elephants) C++14
26 / 100
 13 ms 16988 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 - 1, 0)) - 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 + 5];
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, 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();
}
 
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 member function 'void block::debug()':
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:73:3: note: in expansion of macro 'forf'
   73 |   forf (i, 0, v.size())
      |   ^~~~
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 2 ms 14680 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 2 ms 14684 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 2 ms 14684 KB Output is correct
7 Incorrect 13 ms 16988 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 2 ms 14684 KB Output is correct
7 Incorrect 13 ms 16988 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 2 ms 14684 KB Output is correct
7 Incorrect 13 ms 16988 KB Output isn't correct
8 Halted 0 ms 0 KB -