Submission #600001

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
600001	2022-07-20T11:28:52 Z	MilosMilutinovic	Dancing Elephants (IOI11_elephants)	C++14	Compilation error	0 ms	0 KB

elephants

/**
 *    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 = sqrt(N);
 
int n, l, x[N], cnt[N], pos[N];
int id[N], order[N];
 
vector<int> idx[N / BLOCK];
 
void BuildBlock(int i) {
  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 <= id[order[n - 1]]; 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;
    for (int j = 0; j < (int) idx[id[i]].size(); j++) {
      if (idx[id[i]][j] != i) {      
        b.push_back(idx[id[i]][j]);
      }
    }
    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; 
}

Compilation message

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:103:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  103 |       int mid = low + high >> 1;
      |                 ~~~~^~~~~~
/usr/bin/ld: /tmp/cct6rSZZ.o: in function `main':
grader.cpp:(.text.startup+0x27): undefined reference to `init(int, int, int*)'
collect2: error: ld returned 1 exit status