Submission #233476

#	Time	Username	Problem	Language	Result	Execution time	Memory
233476		crossing0ver	Dancing Elephants (IOI11_elephants)	C++17	0 / 100	5 ms	384 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; 
int update(int i, int y) {
 P[i] = y; 
 //s[g[i]] = y;
  int pos = g[i];
  for (;pos < n && 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: 0 / 10
• Subtask 2: 0 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3