oj.uz

답안 #600126

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
600126 2022-07-20T13:23:43 Z MilosMilutinovic 코끼리 (Dancing Elephants) (IOI11_elephants) C++14
50 / 100
 5773 ms 2420 KB 
/**
 *    author:  wxhtzdy
 *    created: 20.07.2022 11:59:55
**/
#include "elephants.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 150005;
const int BLOCK = sqrt(MAX);
 
int n, l, x[MAX], cnt[MAX], pos[MAX];
int id[MAX], order[MAX];
 
vector<int> idx[MAX / BLOCK + 5];
 
void BuildBlock(int i) {
  sort(idx[i].begin(), idx[i].end(), [&](int a, int b) {
    if (x[a] != x[b]) {
      return x[a] < x[b];
    } else {
      return a < b;
    }
  });
  int sz = (int) idx[i].size();
  int ptr = sz - 1;    
  for (int j = sz - 1; j >= 0; j--) {
    assert(id[idx[i][j]] == i);
    if (j + 1 < sz) {
      assert(x[idx[i][j]] <= x[idx[i][j + 1]]);
    }
    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) {
    if (x[i] != x[j]) {
      return x[i] < x[j];
    } else {
      return i < 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;
 
bool first = true;
 
int update(int i, int y) {
  ++Q;
  x[i] = y;
  if (Q == BLOCK / 7) {
    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]] <= x[i]) {
        id[i] = j;
        break;
      } 
    }        
    idx[id[i]].push_back(i);
    /*if (idx[id[i]].empty() || x[idx[id[i]].back()] < y) {
    } 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]);
  } 
  int lst = -1;       
  for (int j = 0; j <= n / BLOCK; j++) {
    if (idx[j].empty()) {
      continue;
    }
    //assert(lst <= x[idx[j][0]]);
    lst = x[idx[j].back()];
  }
  //Build(); // brute force check
  int ans = 0, R = -1;
  for (int j = 0; j <= n / BLOCK; j++) {
    if (idx[j].empty() || x[idx[j].back()] <= R) {
      continue;
    }                                          
    int low = 0, high = (int) idx[j].size() - 1, at = 0;
    while (low <= high) {
      int mid = low + high >> 1;
      if (x[idx[j][mid]] > R) {
        at = mid;
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
    assert(R < x[idx[j][at]] && (at == 0 || R >= x[idx[j][at - 1]]));
    ans += cnt[idx[j][at]];
    R = pos[idx[j][at]];
  }
  if (false) {
    for (int i = 0; i < n; i++) {
      order[i] = i;
    }
    sort(order, order + n, [&](int i, int j) {
      return x[i] < x[j];
    });     
    int nans = 0;
    for (int i = 0; i < n; i++) {
      int ptr = i;
      while (ptr + 1 < n && x[order[ptr + 1]] <= x[order[i]] + l) {
        ptr += 1;
      }
      i = ptr;
      nans += 1;
    }
    assert(nans == ans);
    first = false;
  }  
  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:132:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  132 |       int mid = low + high >> 1;
      |                 ~~~~^~~~~~
elephants.cpp:116:7: warning: variable 'lst' set but not used [-Wunused-but-set-variable]
  116 |   int lst = -1;
      |       ^~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1694 ms 1288 KB Output is correct
8 Correct 1892 ms 1428 KB Output is correct
9 Correct 3088 ms 2420 KB Output is correct
10 Correct 3262 ms 2360 KB Output is correct
11 Correct 3196 ms 2360 KB Output is correct
12 Correct 5773 ms 2360 KB Output is correct
13 Correct 3242 ms 2360 KB Output is correct

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1694 ms 1288 KB Output is correct
8 Correct 1892 ms 1428 KB Output is correct
9 Correct 3088 ms 2420 KB Output is correct
10 Correct 3262 ms 2360 KB Output is correct
11 Correct 3196 ms 2360 KB Output is correct
12 Correct 5773 ms 2360 KB Output is correct
13 Correct 3242 ms 2360 KB Output is correct
14 Incorrect 2426 ms 1668 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1694 ms 1288 KB Output is correct
8 Correct 1892 ms 1428 KB Output is correct
9 Correct 3088 ms 2420 KB Output is correct
10 Correct 3262 ms 2360 KB Output is correct
11 Correct 3196 ms 2360 KB Output is correct
12 Correct 5773 ms 2360 KB Output is correct
13 Correct 3242 ms 2360 KB Output is correct
14 Incorrect 2426 ms 1668 KB Output isn't correct
15 Halted 0 ms 0 KB -