oj.uz

Submission #600019

# Submission time Handle Problem Language Result Execution time Memory
600019 2022-07-20T11:52:41 Z MilosMilutinovic Dancing Elephants (IOI11_elephants) C++14
26 / 100
 9000 ms 2468 KB 
/**
 *    author:  wxhtzdy
 *    created: 20.07.2022 11:59:55
**/
#include "elephants.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 150005;
const int BLOCK = 3;

int n, l, x[N], cnt[N], pos[N];
int id[N], order[N];

vector<int> idx[N / BLOCK];

void BuildBlock(int i) {
  sort(idx[i].begin(), idx[i].end(), [&](int a, int b) {
    return x[a] < x[b];
  });
  int sz = (int) idx[i].size();
  int ptr = sz - 1;    
  for (int j = sz - 1; j >= 0; j--) {
    if (x[idx[i][sz - 1]] - x[idx[i][j]] <= l) {
      cnt[idx[i][j]] = 1;
      pos[idx[i][j]] = x[idx[i][j]] + l;
    } else { 
      while (x[idx[i][ptr]] - x[idx[i][j]] > l) {
        ptr -= 1;
      }
      cnt[idx[i][j]] = cnt[idx[i][ptr + 1]] + 1;
      pos[idx[i][j]] = pos[idx[i][ptr + 1]];
    }                              
  }
}

void Build() {     
  for (int i = 0; i < n; i++) {
    order[i] = i;
  }
  sort(order, order + n, [&](int i, int j) {
    return x[i] < x[j];
  });
  for (int i = 0; i <= n / BLOCK; i++) {
    idx[i].clear();
  }
  for (int i = 0; i < n; i++) {
    id[order[i]] = i / BLOCK;
    idx[id[order[i]]].push_back(order[i]);
  }
  for (int i = 0; i <= n / BLOCK; i++) {
    BuildBlock(i);
  }
}

int Q;

int update(int i, int y) {
  ++Q;
  x[i] = y;
  if (Q == BLOCK / 2) {
    Build();
    Q = 0;
  } else {
    vector<int> b;
    bool found = false;
    for (int j = 0; j < (int) idx[id[i]].size(); j++) {
      if (idx[id[i]][j] != i) {      
        b.push_back(idx[id[i]][j]);
      } else {
        found = true;
      }
    }
    assert(found);
    idx[id[i]] = b;
    BuildBlock(id[i]);
    b.clear();
    for (int j = n / BLOCK; j >= 0; j--) {
      if (!idx[j].empty() && x[idx[j][0]] <= y) {
        id[i] = j;
        break;
      } 
    }        
    if (idx[id[i]].empty() || x[idx[id[i]].back()] < y) {
      idx[id[i]].push_back(i);
    } else {
      vector<int> b;    
      for (int j = 0; j < (int) idx[id[i]].size(); j++) {
        if (y <= x[idx[id[i]][j]]) {
          b.push_back(i);
          y = (int) 1.01e9;
          j -= 1;
        } else {
          b.push_back(idx[id[i]][j]);
        }
      }
      idx[id[i]] = b;
    }
    BuildBlock(id[i]);
  } 
  //Build(); // brute force check
  int ans = 0, R = -1;
  for (int i = 0; i <= n / BLOCK; i++) {
    if (idx[i].empty() || x[idx[i].back()] <= R) {
      continue;
    }                                          
    int low = 0, high = (int) idx[i].size() - 1, at = 0;
    while (low <= high) {
      int mid = low + high >> 1;
      if (x[idx[i][mid]] > R) {
        at = mid;
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
    ans += cnt[idx[i][at]];
    R = pos[idx[i][at]];
  }       
  return ans; 
}

void init(int n, int l, int x[]) {
  ::n = n;
  ::l = l;
  for (int i = 0; i < n; i++) {
    ::x[i] = x[i];
  }
  Build();
}

Compilation message

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:110:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  110 |       int mid = low + high >> 1;
      |                 ~~~~^~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 2 ms 1492 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 2 ms 1492 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Execution timed out 9018 ms 2468 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 2 ms 1492 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Execution timed out 9018 ms 2468 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 2 ms 1492 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Execution timed out 9018 ms 2468 KB Time limit exceeded
8 Halted 0 ms 0 KB -