oj.uz

Submission #754113

# Submission time Handle Problem Language Result Execution time Memory
754113 2023-06-06T17:54:32 Z nicksms Dancing Elephants (IOI11_elephants) C++17
100 / 100
 5026 ms 7368 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#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=950;
int pos[MAXN],j[MAXN],h[MAXN],ord[MAXN],w[MAXN];
int buck[MAXN/BS + 5][3*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, int hint=0) {
  if (s[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] || hint >= s[i]) return;
  j[buck[i][0]]=pos[buck[i][0]]-l,h[buck[i][0]]=1;
  int lp = 0;
  if (hint > 10) lp = max(lp, llt(i,pos[buck[i][hint]]-l));
  for (int k = max(1,hint); 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));
  int ind = s[w[i]]-1;
  for (int k = llt(w[i],pos[i])+1; k < s[w[i]]-1; k++) {
    if (buck[w[i]][k]==i) {
      ind=k;
      break;
    }
  }
  memmove(buck[w[i]] + ind, buck[w[i]] + ind + 1, (s[w[i]]-ind)*sizeof(int));
  s[w[i]]--;
  fixbuck(w[i],ind);
  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;
  }
  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];
  // }
  memmove(buck[w[i]]+ind+1,buck[w[i]]+ind,(s[w[i]]-ind)*sizeof(int));
  buck[w[i]][ind]=i;
  fixbuck(w[i],ind);
  // 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

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 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 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 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 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 432 ms 1312 KB Output is correct
8 Correct 458 ms 1484 KB Output is correct
9 Correct 491 ms 2516 KB Output is correct
10 Correct 430 ms 2516 KB Output is correct
11 Correct 387 ms 2520 KB Output is correct
12 Correct 771 ms 2664 KB Output is correct
13 Correct 421 ms 2528 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 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 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 432 ms 1312 KB Output is correct
8 Correct 458 ms 1484 KB Output is correct
9 Correct 491 ms 2516 KB Output is correct
10 Correct 430 ms 2516 KB Output is correct
11 Correct 387 ms 2520 KB Output is correct
12 Correct 771 ms 2664 KB Output is correct
13 Correct 421 ms 2528 KB Output is correct
14 Correct 461 ms 1856 KB Output is correct
15 Correct 708 ms 1928 KB Output is correct
16 Correct 1282 ms 2872 KB Output is correct
17 Correct 1397 ms 3500 KB Output is correct
18 Correct 1487 ms 3520 KB Output is correct
19 Correct 955 ms 3380 KB Output is correct
20 Correct 1340 ms 3544 KB Output is correct
21 Correct 1384 ms 3556 KB Output is correct
22 Correct 746 ms 3376 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 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 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 432 ms 1312 KB Output is correct
8 Correct 458 ms 1484 KB Output is correct
9 Correct 491 ms 2516 KB Output is correct
10 Correct 430 ms 2516 KB Output is correct
11 Correct 387 ms 2520 KB Output is correct
12 Correct 771 ms 2664 KB Output is correct
13 Correct 421 ms 2528 KB Output is correct
14 Correct 461 ms 1856 KB Output is correct
15 Correct 708 ms 1928 KB Output is correct
16 Correct 1282 ms 2872 KB Output is correct
17 Correct 1397 ms 3500 KB Output is correct
18 Correct 1487 ms 3520 KB Output is correct
19 Correct 955 ms 3380 KB Output is correct
20 Correct 1340 ms 3544 KB Output is correct
21 Correct 1384 ms 3556 KB Output is correct
22 Correct 746 ms 3376 KB Output is correct
23 Correct 3447 ms 6820 KB Output is correct
24 Correct 3722 ms 6828 KB Output is correct
25 Correct 3074 ms 6820 KB Output is correct
26 Correct 3079 ms 6824 KB Output is correct
27 Correct 4642 ms 6824 KB Output is correct
28 Correct 1828 ms 2252 KB Output is correct
29 Correct 1873 ms 2248 KB Output is correct
30 Correct 1785 ms 2248 KB Output is correct
31 Correct 1853 ms 2248 KB Output is correct
32 Correct 2778 ms 6820 KB Output is correct
33 Correct 1681 ms 6864 KB Output is correct
34 Correct 2908 ms 6824 KB Output is correct
35 Correct 2087 ms 7368 KB Output is correct
36 Correct 1540 ms 6820 KB Output is correct
37 Correct 4471 ms 7224 KB Output is correct
38 Correct 2887 ms 6820 KB Output is correct
39 Correct 3492 ms 6824 KB Output is correct
40 Correct 2964 ms 6828 KB Output is correct
41 Correct 4979 ms 6848 KB Output is correct
42 Correct 5026 ms 7108 KB Output is correct