oj.uz

답안 #132568

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
132568 2019-07-19T07:34:06 Z tmwilliamlin168 코끼리 (Dancing Elephants) (IOI11_elephants) C++14
0 / 100
 8 ms 7416 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;

const int mxN=1.5e5, B=1, mxBC=(mxN-1)/B+1;
int n, l, *x, uc, bc, r[mxBC];
map<int, int> mp;
vector<int> v[mxBC];
vector<array<int, 2>> w[mxBC];

void init(int N, int L, int X[]) {
	n=N;
	l=L;
	x=X;
	for(int i=0; i<n; ++i)
		++mp[x[i]];
}

void bb(int i) {
	w[i]=vector<array<int, 2>>(v[i].size());
	for(int j1=(int)v[i].size()-1, j2=v[i].size(); ~j1; --j1) {
		while(v[i][j2-1]>v[i][j1]+l)
			--j2;
		w[i][j1]=j2<v[i].size()?array<int, 2>{w[i][j2][0]+1, w[i][j2][1]}:array<int, 2>{1, v[i][j1]+l};
	}
}
void bld() {
	bc=0;
	for(pair<int, int> p : mp) {
		if(!bc||v[bc-1].size()>=B)
			v[bc++].clear();
		v[bc-1].push_back(p.first);
	}
	for(int i=0; i<bc; ++i) {
		r[i]=i+1<bc?v[i+1][0]-1:1e9;
		bb(i);
	}
}

void upd(int x, bool a) {
	int c=-1;
	while(x>r[++c]);
	int p=lower_bound(v[c].begin(), v[c].end(), x)-v[c].begin();
	if(a)
		v[c].insert(v[c].begin()+p, x);
	else
		v[c].erase(v[c].begin()+p);
	bb(c);
}

int update(int i, int y) {
	if(uc++%B==0)
		bld();
	--mp[x[i]];
	if(!mp[x[i]])
		upd(x[i], 0);
	if(!mp[y])
		upd(y, 1);
	++mp[y];
	x[i]=y;
	int a=0;
	for(int i=0, c=-1; i<bc; ++i) {
		int p=upper_bound(v[i].begin(), v[i].end(), c)-v[i].begin();
		if(p<v[i].size()) {
			a+=w[i][p][0];
			c=w[i][p][1];
		}
	}
	return a;
}

Compilation message

elephants.cpp: In function 'void bb(int)':
elephants.cpp:24:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   w[i][j1]=j2<v[i].size()?array<int, 2>{w[i][j2][0]+1, w[i][j2][1]}:array<int, 2>{1, v[i][j1]+l};
            ~~^~~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:64:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(p<v[i].size()) {
      ~^~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 7416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 7416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 7416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 7416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 7416 KB Output isn't correct
2 Halted 0 ms 0 KB -