oj.uz

Submission #833705

# Submission time Handle Problem Language Result Execution time Memory
833705 2023-08-22T08:04:21 Z ttamx Dancing Elephants (IOI11_elephants) C++14
26 / 100
 7971 ms 4460 KB 
#include "elephants.h"
#include<bits/stdc++.h>

using namespace std;

const int N=150005;
const int K=390;
const int inf=1e9;

int n,L;
int X[N];

struct elephant{
	int id,pos,needed,covered;
	elephant(){}
	elephant(int id,int pos):id(id),pos(pos){}
	bool operator<(const elephant &o)const{
		return pos<o.pos;
	}
}elep[N];

vector<elephant> block[K];
int blockid[N];

void computeblock(int i){
	deque<elephant> dq;
	for(int j=block[i].size()-1;j>=0;j--){
		assert(j==0||block[i][j].pos>block[i][j-1].pos);
		if(dq.empty()||block[i][j].pos+L>=dq.back().pos){
			block[i][j].needed=1;
			block[i][j].covered=block[i][j].pos+L;
		}else{
			while(dq.size()>1&&dq.end()[-2].pos>block[i][j].pos+L)dq.pop_back();
			block[i][j].needed=dq.back().needed+1;
			block[i][j].covered=dq.back().covered;
		}
		dq.emplace_front(block[i][j]);
	}
}

void build(){
	for(int i=0;i<K;i++)block[i].clear();
	for(int i=0;i<n;i++){
		block[i/K].emplace_back(elep[i]);
		blockid[elep[i].id]=i/K;
	}
	for(int i=0;i<K;i++)computeblock(i);
}

void init(int N, int _L, int _X[]){
	n=N,L=_L;
	for(int i=0;i<n;i++)X[i]=_X[i];
	for(int i=0;i<n;i++)elep[i]=elephant(i,X[i]);
	build();
}

int findblock(int pos){
	int l=0,r=K-1;
	while(l<r){
		int m=(l+r+1)/2;
		if(!block[m].empty()&&block[m][0].pos<=pos)l=m;
		else r=m-1;
	}
	return l;
}

int counter=0;

int update(int i, int y){
	if(counter==K){
		counter=0;
		int idx=0;
		for(int j=0;j<K;j++)for(auto e:block[j])elep[idx++]=e;
		sort(elep,elep+n);
	}
	counter++;
	int id=blockid[i];
	auto it=block[id].begin();
	while(it->id!=i)it++;
	auto tmp=*it;
	block[id].erase(it);
	computeblock(id);
	X[i]=y;
	tmp.pos=y;
	id=findblock(X[i]);
	blockid[i]=id;
	it=block[id].begin();
	while(it!=block[id].end()&&it->pos<=X[i])it++;
	block[id].insert(it,tmp);
	computeblock(id);
	int ans=0;
	int pos=-inf;
	for(int i=0;i<K;i++){
		auto it=upper_bound(block[i].begin(),block[i].end(),elephant(-1,pos));
		if(it==block[i].end())continue;
		ans+=it->needed;
		pos=it->covered;
	}
	return ans;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 497 ms 1528 KB Output is correct
8 Correct 504 ms 1768 KB Output is correct
9 Correct 609 ms 3332 KB Output is correct
10 Incorrect 7971 ms 4460 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 497 ms 1528 KB Output is correct
8 Correct 504 ms 1768 KB Output is correct
9 Correct 609 ms 3332 KB Output is correct
10 Incorrect 7971 ms 4460 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 497 ms 1528 KB Output is correct
8 Correct 504 ms 1768 KB Output is correct
9 Correct 609 ms 3332 KB Output is correct
10 Incorrect 7971 ms 4460 KB Output isn't correct
11 Halted 0 ms 0 KB -