제출 #233484

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
233484		crossing0ver	Dancing Elephants (IOI11_elephants)	C++17	26 / 100	9020 ms	3340 KiB

elephants

#include <bits/stdc++.h>
#include "elephants.h"
using namespace std;
int n,L,P[100000];
int s[100000],g[100000];
bool cmp(int a,int b) {
	return P[a] < P[b];
	
}
void init(int N, int L1, int X[])
{
  n = N; L = L1; 
  for (int i = 0; i < n; i++) s[i] = i,P[i] = X[i];
  sort(s,s+n,cmp);
  for (int i = 0; i < n; i++) g[s[i]] = i;
}
int last,ans,pos; 
int update(int i, int y) {
  P[i] = y; 
   pos = g[i];
  for (;pos < n - 1 && y > P[ s[pos + 1 ] ]; pos++) {
  	g[ s[pos + 1 ]]--;
  	swap(s[pos],s[pos + 1]);  
  }
  for (;pos > 0 && y < P[ s[pos - 1 ] ]; pos--) {
  	g[ s[pos - 1 ]]++;
  	swap(s[pos],s[pos - 1]);  
  }
  g[i] = pos;
  ans = 0;
  last = -1;
  for (i = 0; i < n; i++)
  	if (last  < P[s[i]]) ans++,last = P[s[i]] + L;
  return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3