oj.uz

Submission #938806

# Submission time Handle Problem Language Result Execution time Memory
938806 2024-03-05T14:50:50 Z pan Dancing Elephants (IOI11_elephants) C++17
26 / 100
 193 ms 22620 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;
		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);
		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 2 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 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
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 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 140 ms 10268 KB Output is correct
8 Correct 145 ms 10492 KB Output is correct
9 Correct 193 ms 12372 KB Output is correct
10 Runtime error 26 ms 22620 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 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 140 ms 10268 KB Output is correct
8 Correct 145 ms 10492 KB Output is correct
9 Correct 193 ms 12372 KB Output is correct
10 Runtime error 26 ms 22620 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 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 140 ms 10268 KB Output is correct
8 Correct 145 ms 10492 KB Output is correct
9 Correct 193 ms 12372 KB Output is correct
10 Runtime error 26 ms 22620 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -