oj.uz

Submission #349611

# Submission time Handle Problem Language Result Execution time Memory
349611 2021-01-18T02:52:23 Z amunduzbaev Dancing Elephants (IOI11_elephants) C++14
100 / 100
 5583 ms 14812 KB 
#include "elephants.h"
 
#ifndef EVAL
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
using namespace std;
 
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define NeedForSpeed ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define Pi acos(-1);
#define mod 1e9+7
#define inf 1e18
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii; 
typedef pair<ll, ll> pll; 
typedef vector<ll> vll;
typedef vector<int> vii;
typedef vector<pll> vpll;
typedef vector<pii> vpii;
template<class T> bool umin(T& a, const T& b) {return a > b? a = b, true:false;}
template<class T> bool umax(T& a, const T& b) {return a < b? a = b, true:false;}
 
const int NN = 2e5+5;
const int B = 1000;
 
int n, a[NN], l, cur;
int sz[NN], bb[NN], asked;
pii tmp[NN];
vpii dp[B], s[B];

void build(int b){
	int last = sz[b] -1;
	for(int i=sz[b]-1;i>=0;i--){
		while(s[b][i].ff +l < s[b][last].ff && last >= i) last--;
		if(last < sz[b]-1) dp[b][i] = {dp[b][last+1].ff+1, dp[b][last+1].ss};
		else dp[b][i] = {0, i};
	}
}

void init(int N, int L, int X[]){
	n = N, l = L;
	for(int i=0;i<cur;i++){
		s[i].clear();
		sz[i] = 0;
	}
	for(int i=0;i<n;i++){
		tmp[i] = {X[i], i};
		a[i] = X[i];
	}
	sort(tmp, tmp+n);
	cur = 0;
	for(int i=0;i<n;i++){
		bb[tmp[i].ss] = cur;
		s[cur].pb(tmp[i]);
		sz[cur]++;
		if(sz[cur] == B) cur++;
	}
	if(sz[cur]) cur++;
	for(int i=0;i<cur;i++){
		dp[i].resize(sz[i]);
		build(i);
	}
}

void rem(int b, pii val){
	int i=0;
	while(s[b][i] != val) i++;
	s[b].erase(s[b].begin() + i);
	sz[b]--;
	dp[b].resize(sz[b]);
	build(b);
}

void sett(int b, pii val){
	s[b].pb(val);
	sz[b]++;
	dp[b].resize(sz[b]);
	bb[val.ss] = b;
	int i = sz[b]-1;
	
	while(i > 0 && s[b][i].ff < s[b][i-1].ff) { swap(s[b][i], s[b][i-1]); i--; }
	build(b);
}

int qq(){
	int last = -1, ans = 0;
	for(int i=0;i<cur;i++){
		if(sz[i]){
			auto pp = ub(all(s[i]), (pii)mp(last, mod)) - s[i].begin();
			if(pp < sz[i]){
				if(dp[i][pp].ff) ans += dp[i][pp].ff, pp = dp[i][pp].ss; 
				last = s[i][pp].ff+l, ans++;
			}
		}
	}return ans;
}
 
int update(int i, int nw){
	if(asked && asked%B == 0) { init(n, l, a); asked = 0; }
	asked++;
	
	rem(bb[i], mp(a[i], i));
	a[i] = nw;
	for(int b = 0; b+1 < cur; b++){
		if(sz[b+1] && s[b+1][0].ff > nw){
			sett(b, {a[i], i});
			//int ans = qq();
			return qq();
		}
	}
	sett(cur-1, {a[i], i});
	//int ans = qq();
	return qq();;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 455 ms 2412 KB Output is correct
8 Correct 483 ms 2796 KB Output is correct
9 Correct 554 ms 4716 KB Output is correct
10 Correct 545 ms 4204 KB Output is correct
11 Correct 531 ms 4148 KB Output is correct
12 Correct 1062 ms 4716 KB Output is correct
13 Correct 579 ms 4076 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 455 ms 2412 KB Output is correct
8 Correct 483 ms 2796 KB Output is correct
9 Correct 554 ms 4716 KB Output is correct
10 Correct 545 ms 4204 KB Output is correct
11 Correct 531 ms 4148 KB Output is correct
12 Correct 1062 ms 4716 KB Output is correct
13 Correct 579 ms 4076 KB Output is correct
14 Correct 668 ms 3820 KB Output is correct
15 Correct 731 ms 3688 KB Output is correct
16 Correct 1780 ms 5316 KB Output is correct
17 Correct 1785 ms 6508 KB Output is correct
18 Correct 1953 ms 6556 KB Output is correct
19 Correct 1101 ms 6000 KB Output is correct
20 Correct 1770 ms 6524 KB Output is correct
21 Correct 1725 ms 6436 KB Output is correct
22 Correct 969 ms 5412 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 455 ms 2412 KB Output is correct
8 Correct 483 ms 2796 KB Output is correct
9 Correct 554 ms 4716 KB Output is correct
10 Correct 545 ms 4204 KB Output is correct
11 Correct 531 ms 4148 KB Output is correct
12 Correct 1062 ms 4716 KB Output is correct
13 Correct 579 ms 4076 KB Output is correct
14 Correct 668 ms 3820 KB Output is correct
15 Correct 731 ms 3688 KB Output is correct
16 Correct 1780 ms 5316 KB Output is correct
17 Correct 1785 ms 6508 KB Output is correct
18 Correct 1953 ms 6556 KB Output is correct
19 Correct 1101 ms 6000 KB Output is correct
20 Correct 1770 ms 6524 KB Output is correct
21 Correct 1725 ms 6436 KB Output is correct
22 Correct 969 ms 5412 KB Output is correct
23 Correct 3272 ms 13352 KB Output is correct
24 Correct 3722 ms 13544 KB Output is correct
25 Correct 2496 ms 13128 KB Output is correct
26 Correct 3032 ms 12720 KB Output is correct
27 Correct 3639 ms 12464 KB Output is correct
28 Correct 2086 ms 5536 KB Output is correct
29 Correct 2079 ms 5484 KB Output is correct
30 Correct 2071 ms 5484 KB Output is correct
31 Correct 2114 ms 5484 KB Output is correct
32 Correct 2775 ms 12140 KB Output is correct
33 Correct 2904 ms 11372 KB Output is correct
34 Correct 2836 ms 12268 KB Output is correct
35 Correct 2806 ms 12544 KB Output is correct
36 Correct 2349 ms 12028 KB Output is correct
37 Correct 4587 ms 14812 KB Output is correct
38 Correct 3097 ms 11256 KB Output is correct
39 Correct 3279 ms 12268 KB Output is correct
40 Correct 3433 ms 11372 KB Output is correct
41 Correct 5460 ms 13200 KB Output is correct
42 Correct 5583 ms 13420 KB Output is correct