Submission #40109

#	Time	Username	Problem	Language	Result	Execution time	Memory
40109		funcsr	Dancing Elephants (IOI11_elephants)	C++14	100 / 100	7042 ms	28376 KiB

elephants

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cassert>
#include "elephants.h"
using namespace std;
#define INF 1145141919
#define rep(i, n) for (int i=0; i<(n); i++)
#define pb push_back
#define all(x) x.begin(), x.end()
#define _1 first
#define _2 second
typedef pair<int, int> P;
const int B = 1500;
const int MAX_S = (150000/B)+10;

int N, L, S;
int A[150000], ord[150000];
vector<int> G[MAX_S];
P dp[MAX_S][3*B];
void recalc(int b) {
  int n = G[b].size();
  if (n == 0) return;
  int h = n-1;
  for (int i=n-1; i>=0; i--) {
    int pos = G[b][i];
    while (h > i && G[b][h-1]-pos > L) h--;
    if (G[b][h]-pos <= L) {
      dp[b][i] = P(pos, 1);
    }
    else {
      dp[b][i] = P(dp[b][h]._1, dp[b][h]._2+1);
    }
  }
  //cout<<"recalc("<<b<<"): {";for(int x: G[b])cout<<x<<",";cout<<"} dp=[";rep(i, G[b].size()) cout<<"("<<dp[b][i]._1<<","<<dp[b][i]._2<<"),";cout<<"]\n";
}
void erase(int b, int val) {
  auto it = find(all(G[b]), val);
  assert(it != G[b].end());
  G[b].erase(it);
  recalc(b);
}
void insert(int b, int val) {
  auto it = upper_bound(all(G[b]), val);
  G[b].insert(it, val);
  recalc(b);
}

void init(int n, int l, int X[]) {
  N = n, L = l;
  rep(i, N) A[i] = X[i];
  S = (N-1)/B+1;
}

int q = 0;
int update(int i, int y) {
  if ((q++) % B == 0) {
    vector<P> xs;
    rep(i, N) xs.pb(P(A[i], i));
    sort(all(xs));
    rep(b, S) G[b].clear();
    rep(i, N) G[i/B].pb(xs[i]._1), ord[xs[i]._2] = i/B;
    rep(b, S) recalc(b);
  }
  erase(ord[i], A[i]);
  int b = 0;
  rep(i, S) {
    if (!G[i].empty() && G[i].front() > y) break;
    b = i;
  }
  insert(b, y);
  ord[i] = b, A[i] = y;
  //rep(b, S) {for (int x:G[b])cout<<x<<",";cout<<"|";}cout<<"\n";
  int c = 0, last = -1;
  rep(b, S) {
    if (G[b].empty()) continue;
    int st = 0;
    if (last != -1) {
      st = upper_bound(all(G[b]), last+L) - G[b].begin();
      if (st == G[b].size()) continue;
    }
    last = dp[b][st]._1;
    c += dp[b][st]._2;
  }
  return c;
}

Compilation message (stderr)

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:81:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if (st == G[b].size()) continue;
              ^

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