oj.uz

Submission #938807

# Submission time Handle Problem Language Result Execution time Memory
938807 2024-03-05T15:03:51 Z pan Dancing Elephants (IOI11_elephants) C++17
50 / 100
 325 ms 14576 KB 
#include "elephants.h"
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include "bits_stdc++.h"
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
using namespace std;
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<ll, pi> pii;
// general
ll range;
vector<ll> x;
// SQRT Data Structure
ll const blksz = 300;
ll blk;
vector<vector<ll> > groups;
vector<vector<pi> > dp;
ll query()
{
	//show(4);
	ll ret = 0;
	ll last = -1;
	for (ll i=0; i<blk; ++i)
	{
		if (groups[i].empty() || groups[i].back()<=last) continue;
		ll ind = ub(groups[i].begin(), groups[i].end(), last)-groups[i].begin();
		ret+=dp[i][ind].f;
		last = dp[i][ind].s;
	}
	return ret;
}
void processblk(ll ind)
{
	//show(3);
	if (groups[ind].empty()) return;
	ll n= groups[ind].size();
	dp[ind].clear();
	dp[ind].resize(n);
	ll r = n-1;
	for (ll l = n-1; l>=0; --l)
	{
		while (r-1>=l && groups[ind][r]-groups[ind][l]>range) {r--;}
		if (r==n-1) dp[ind][l] = mp(1, groups[ind][l] + range);
		else  dp[ind][l] = dp[ind][r+1], dp[ind][l].f++;
	}
}
void remove(ll pos)
{
	//show(1);
	ll i;
	for (i=0; i<blk; ++i)
	{
		if (groups[i].empty()) continue;
		if (groups[i][0]<=pos && groups[i].back()>=pos) break;
	}
	groups[i].erase(lb(groups[i].begin(), groups[i].end(), pos));
	processblk(i);
}
void insert(ll pos)
{
	//show(1);
	ll i;
	for (i=0; i<blk; ++i)
	{
		if (groups[i].empty()) continue;
		if (groups[i][0]>=pos) break;
	}
	if (i) i--;
	groups[i].insert(ub(groups[i].begin(), groups[i].end(), pos), pos);
	if (groups[i].size()>=2*blksz)
	{
		vector<ll> neww;
		vector<pi> emp;
		ll half = groups[i].size()/2;
		while (half--) {neww.pb(groups[i].back()); groups[i].pop_back();}
		reverse(neww.begin(), neww.end());
		groups.insert(groups.begin()+i+1, neww);
		dp.insert(dp.begin()+i+1, emp);
		processblk(i);
		processblk(i+1);
		blk++;
	}
	else {processblk(i);}
}

void init(int N, int L, int X[])
{
	range = L;
	x.resize(N);
	blk = (N-1)/blksz + 1;
	groups.resize(blk);
	dp.resize(blk);
	for (ll i=0; i<N; ++i) groups[i/blksz].pb(X[i]);
	for (ll i=0; i<blk; ++i) processblk(i);
	for (ll i=0; i<N; ++i) x[i] = X[i];
}
int update(int i, int y)
{
	//show("FUCK");
	remove(x[i]);
	insert(y);
	x[i] = y;
	return query();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6644 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6644 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6644 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 150 ms 9356 KB Output is correct
8 Correct 156 ms 9604 KB Output is correct
9 Correct 191 ms 10832 KB Output is correct
10 Correct 203 ms 13412 KB Output is correct
11 Correct 176 ms 14576 KB Output is correct
12 Correct 325 ms 12864 KB Output is correct
13 Correct 223 ms 14528 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6644 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 150 ms 9356 KB Output is correct
8 Correct 156 ms 9604 KB Output is correct
9 Correct 191 ms 10832 KB Output is correct
10 Correct 203 ms 13412 KB Output is correct
11 Correct 176 ms 14576 KB Output is correct
12 Correct 325 ms 12864 KB Output is correct
13 Correct 223 ms 14528 KB Output is correct
14 Incorrect 152 ms 12268 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6644 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 150 ms 9356 KB Output is correct
8 Correct 156 ms 9604 KB Output is correct
9 Correct 191 ms 10832 KB Output is correct
10 Correct 203 ms 13412 KB Output is correct
11 Correct 176 ms 14576 KB Output is correct
12 Correct 325 ms 12864 KB Output is correct
13 Correct 223 ms 14528 KB Output is correct
14 Incorrect 152 ms 12268 KB Output isn't correct
15 Halted 0 ms 0 KB -