oj.uz

Submission #40109

# Submission time Handle Problem Language Result Execution time Memory
40109 2018-01-27T08:15:14 Z funcsr Dancing Elephants (IOI11_elephants) C++14
100 / 100
 7042 ms 28376 KB 
#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

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.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 698 ms 23088 KB Output is correct
2 Correct 716 ms 23368 KB Output is correct
3 Correct 817 ms 24056 KB Output is correct
4 Correct 613 ms 24060 KB Output is correct
5 Correct 578 ms 24060 KB Output is correct
6 Correct 1580 ms 24068 KB Output is correct
7 Correct 680 ms 24060 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 863 ms 23420 KB Output is correct
2 Correct 1059 ms 23400 KB Output is correct
3 Correct 2744 ms 24056 KB Output is correct
4 Correct 2632 ms 25212 KB Output is correct
5 Correct 2810 ms 25212 KB Output is correct
6 Correct 1337 ms 25196 KB Output is correct
7 Correct 2625 ms 25212 KB Output is correct
8 Correct 2369 ms 25212 KB Output is correct
9 Correct 1105 ms 25196 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4049 ms 27660 KB Output is correct
2 Correct 4523 ms 27660 KB Output is correct
3 Correct 3033 ms 27660 KB Output is correct
4 Correct 4117 ms 27668 KB Output is correct
5 Correct 4276 ms 27668 KB Output is correct
6 Correct 4934 ms 22828 KB Output is correct
7 Correct 4741 ms 22828 KB Output is correct
8 Correct 4862 ms 22828 KB Output is correct
9 Correct 4763 ms 22828 KB Output is correct
10 Correct 3426 ms 27668 KB Output is correct
11 Correct 3262 ms 27668 KB Output is correct
12 Correct 3306 ms 27668 KB Output is correct
13 Correct 2850 ms 27668 KB Output is correct
14 Correct 2722 ms 27668 KB Output is correct
15 Correct 5214 ms 28376 KB Output is correct
16 Correct 3356 ms 27668 KB Output is correct
17 Correct 3389 ms 27668 KB Output is correct
18 Correct 3372 ms 27668 KB Output is correct
19 Correct 6844 ms 27684 KB Output is correct
20 Correct 7042 ms 27668 KB Output is correct