oj.uz

Submission #406232

# Submission time Handle Problem Language Result Execution time Memory
406232 2021-05-17T09:45:37 Z pure_mem Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 12644 KB 
#include "elephants.h"
#include <bits/stdc++.h>

#define X first
#define Y second
#define MP make_pair
#define ll long long

using namespace std;

const int MAXN = 150000, BS = 300, INF = 1e9 + 7;

int n, w, p[MAXN], ps[MAXN], buck[MAXN];
vector< pair< int, int > > bl[MAXN / BS + 3];
int dp1[MAXN], dp2[MAXN];

void trick(vector< pair<int, int> > &cur, pair<int, int> val){
	vector< pair<int, int> > tmp;
	for(pair<int, int> v: cur){
		if(val == v)
			continue;
		tmp.push_back(v);
	}
	cur.swap(tmp), tmp.clear();
}

void upd(int id, bool keep = 0){		
	if(!keep)
		sort(bl[id].begin(), bl[id].end());
	for(int i = (int)bl[id].size() - 1, j = (int)bl[id].size();i >= 0;i--){
		int me = bl[id][i].Y, pos = bl[id][i].X;
		buck[me] = id;
		while(j - 1 >= i && bl[id][j - 1].X > pos + w) j--;
		if(j == (int)bl[id].size()) dp1[me] = 1, dp2[me] = pos + w;
		else dp1[me] = dp1[bl[id][j].Y] + 1, dp2[me] = dp2[bl[id][j].Y]; 	
	}		
}

void build(){		
	sort(ps, ps + n, [](int x, int y){return p[x] < p[y];});
	for(int i = 0, j = 0;i < n;i += BS, j++)
		bl[j].clear();
	for(int i = 0, j = 0, z = 1;i < n;i++, (z == BS ? z = 1, j++: z++))
		bl[j].push_back(MP(p[ps[i]], ps[i]));
	for(int i = 0, j = 0;i < n;i += BS, j++)
		upd(j, 1);
}

void init(int N, int L, int X[]){
  	n = N, w = L;
  	for(int i = 0;i < n;i++)
    	p[i] = X[i], ps[i] = i; 
	build();
}

int solve(){
	int cnt = 0, pos = 0;
	for(int j = 0;;j++){
		if(bl[j].empty())
			break;
		else if(bl[j].back().X < pos)
			continue;
		pair<int, int> tmp = *upper_bound(bl[j].begin(), bl[j].end(), MP(pos, -1));
		cnt += dp1[tmp.Y], pos = dp2[tmp.Y] + 1;
	}	
	return cnt;
}

int cntQ;

int update(int i, int y){
  	cntQ++;
  	if(cntQ == BS){
    	p[i] = y, cntQ = 0;
    	build();
  	}
  	else{ 
  		trick(bl[buck[i]], MP(p[i], i)), upd(buck[i]);
  		p[i] = y;
  		for(int j = 0;;j++){
  			int left = (j ? bl[j - 1].back().X: 0), right = (bl[j + 1].empty() ? INF: bl[j + 1][0].X);
  			if(left <= y && y <= right){
  				bl[j].push_back(MP(y, i)), upd(j);
  				break;
  			}
  		}
  	}
  	return solve();
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 997 ms 2308 KB Output is correct
8 Correct 1025 ms 2592 KB Output is correct
9 Correct 1162 ms 4344 KB Output is correct
10 Correct 1597 ms 4224 KB Output is correct
11 Correct 1553 ms 4068 KB Output is correct
12 Correct 1959 ms 4224 KB Output is correct
13 Correct 1641 ms 3920 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 997 ms 2308 KB Output is correct
8 Correct 1025 ms 2592 KB Output is correct
9 Correct 1162 ms 4344 KB Output is correct
10 Correct 1597 ms 4224 KB Output is correct
11 Correct 1553 ms 4068 KB Output is correct
12 Correct 1959 ms 4224 KB Output is correct
13 Correct 1641 ms 3920 KB Output is correct
14 Correct 1392 ms 3600 KB Output is correct
15 Correct 1580 ms 3452 KB Output is correct
16 Correct 2637 ms 4932 KB Output is correct
17 Correct 3329 ms 5828 KB Output is correct
18 Correct 3608 ms 5716 KB Output is correct
19 Correct 3970 ms 5920 KB Output is correct
20 Correct 3477 ms 5780 KB Output is correct
21 Correct 3568 ms 5756 KB Output is correct
22 Correct 2956 ms 5352 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 997 ms 2308 KB Output is correct
8 Correct 1025 ms 2592 KB Output is correct
9 Correct 1162 ms 4344 KB Output is correct
10 Correct 1597 ms 4224 KB Output is correct
11 Correct 1553 ms 4068 KB Output is correct
12 Correct 1959 ms 4224 KB Output is correct
13 Correct 1641 ms 3920 KB Output is correct
14 Correct 1392 ms 3600 KB Output is correct
15 Correct 1580 ms 3452 KB Output is correct
16 Correct 2637 ms 4932 KB Output is correct
17 Correct 3329 ms 5828 KB Output is correct
18 Correct 3608 ms 5716 KB Output is correct
19 Correct 3970 ms 5920 KB Output is correct
20 Correct 3477 ms 5780 KB Output is correct
21 Correct 3568 ms 5756 KB Output is correct
22 Correct 2956 ms 5352 KB Output is correct
23 Correct 7480 ms 12640 KB Output is correct
24 Correct 8180 ms 12644 KB Output is correct
25 Correct 6862 ms 12636 KB Output is correct
26 Execution timed out 9045 ms 12608 KB Time limit exceeded
27 Halted 0 ms 0 KB -