oj.uz

답안 #754089

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
754089 2023-06-06T16:50:49 Z nicksms 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
50 / 100
 1025 ms 2516 KB 
#include "elephants.h"
/**
 *      Author:  Nicholas Winschel
 *      Created: 06.06.2023 11:07:24
**/

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=long double;
template<class T> using V=vector<T>;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int,int>;
#define f first
#define s second
#define sz(x) (int)((x).size())

int n,l;
const int MAXN=150000;
const int BS=500;
int pos[MAXN],j[MAXN],h[MAXN],ord[MAXN],w[MAXN];
int buck[MAXN/BS + 5][2*BS+1],s[MAXN/BS+5];
int cnt = 0;

int llt(int v, int x) {
  if (!s[v] || pos[buck[v][0]] >= x) return -1;
  int l = 0,r=s[v];
  while (r-l>1) {
    int m = (l+r)>>1;
    if (pos[buck[v][m]] >= x) r=m;
    else l=m;
  }
  return l;
}

void fixbuck(int i) {
  // if (sz(buck[i])>=2*BS) cnt=2*BS;
  // cerr << "fb: " << i << endl;
  // for (int x =0; x < s[i]; x++) cerr << buck[i][x] << " ";
  // cerr << endl;
  if (!s[i]) return;
  j[buck[i][0]]=pos[buck[i][0]]-l,h[buck[i][0]]=1;
  int lp = 0;
  for (int k = 1; k < s[i]; k++) {
    while (lp < s[i]-1 && pos[buck[i][lp+1]]<pos[buck[i][k]]-l) lp++;
    if (pos[buck[i][lp]] < pos[buck[i][k]]-l) {
      // cerr << "test" << endl;
      j[buck[i][k]]=j[buck[i][lp]];
      h[buck[i][k]]=h[buck[i][lp]]+1;
    } else {
      j[buck[i][k]]=pos[buck[i][k]]-l;
      h[buck[i][k]]=1;
    }
  }
}

void fixall() {
  // cerr << "REALLOC" << endl;
  int cur = 0;
  for (int i = 0; i <= (n-1)/BS; i++) {
    for (int x = 0; x < s[i]; x++) ord[cur++]=buck[i][x];
  }
  int c = 0;
  for (int i = 0; i < n; i++) {
    buck[i/BS][c++]=ord[i];
    w[ord[i]]=i/BS;
    if (i == n-1 || (i+1)/BS != i/BS) s[i/BS]=(c),c=0,fixbuck(i/BS);
  }
}

void init(int N, int L, int X[])
{
  n = N;
  l = L;
  memcpy(pos,X,N*sizeof(int));
  for (int i = 0; i < N; i++) {
    buck[i/BS][s[i/BS]++]=(i);
  }
  fixall();
}

int update(int i, int y)
{
  // cerr << "mov: " << i << " " << y << endl;
  if (cnt++ > BS) fixall(),cnt=0;
  // buck[w[i]].erase(find(buck[w[i]].begin(),buck[w[i]].end(),i));
  for (int k = 0; k < s[w[i]]-1; k++) {
    if (buck[w[i]][k]==i) {
      for (int kk = k; kk < s[w[i]]-1; kk++) buck[w[i]][kk]=buck[w[i]][kk+1];
      break;
    }
  }
  s[w[i]]--;
  fixbuck(w[i]);
  pos[i]=y;
  w[i]=0;
  for (int k = 0; k <= (n-1)/BS; k++) {
    if (s[k] && pos[buck[k][0]] < pos[i]) w[i]=k;
  }
  int ind = llt(w[i],pos[i])+1;
  // buck[w[i]].insert(buck[w[i]].begin()+ind,i);
  s[w[i]]++;
  // cerr << "dbg2: " << ind << endl;
  for (int k = s[w[i]]-1; k > ind; k--) {
    // cerr << k << " " << buck[w[i]][k] << " " << buck[w[i]][k-1] << endl;
    buck[w[i]][k]=buck[w[i]][k-1];
  }
  buck[w[i]][ind]=i;
  fixbuck(w[i]);
  // for (int i = 0; i < n; i++) {
  //   cerr << "dbg: " << i << " " << pos[i] << " " << j[i] << " " << h[i] << endl; 
  // }
  int cur = 2e9,ret=0;
  for (int i = (n-1)/BS; i >= 0; i--) {
    int ind = llt(i,cur);
    if (ind >= 0) {
      ind=buck[i][ind];
      cur=j[ind],ret += h[ind];
      // cerr << "jmp: " << cur << " " << ret << endl;
    }
  }
  return ret;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 268 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 524 ms 1324 KB Output is correct
8 Correct 574 ms 1476 KB Output is correct
9 Correct 694 ms 2496 KB Output is correct
10 Correct 663 ms 2516 KB Output is correct
11 Correct 586 ms 2516 KB Output is correct
12 Correct 1025 ms 2504 KB Output is correct
13 Correct 681 ms 2516 KB Output is correct

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 268 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 524 ms 1324 KB Output is correct
8 Correct 574 ms 1476 KB Output is correct
9 Correct 694 ms 2496 KB Output is correct
10 Correct 663 ms 2516 KB Output is correct
11 Correct 586 ms 2516 KB Output is correct
12 Correct 1025 ms 2504 KB Output is correct
13 Correct 681 ms 2516 KB Output is correct
14 Incorrect 137 ms 1620 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 268 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 524 ms 1324 KB Output is correct
8 Correct 574 ms 1476 KB Output is correct
9 Correct 694 ms 2496 KB Output is correct
10 Correct 663 ms 2516 KB Output is correct
11 Correct 586 ms 2516 KB Output is correct
12 Correct 1025 ms 2504 KB Output is correct
13 Correct 681 ms 2516 KB Output is correct
14 Incorrect 137 ms 1620 KB Output isn't correct
15 Halted 0 ms 0 KB -