oj.uz

Submission #754127

# Submission time Handle Problem Language Result Execution time Memory
754127 2023-06-06T18:16:48 Z nicksms Dancing Elephants (IOI11_elephants) C++17
100 / 100
 6912 ms 7796 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=600,OBS=950;
int pos[MAXN],j[MAXN],h[MAXN],ord[MAXN],w[MAXN];
int buck[MAXN/BS + 5][3*OBS+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*OBS) 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 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 327 ms 1344 KB Output is correct
8 Correct 377 ms 1508 KB Output is correct
9 Correct 531 ms 2616 KB Output is correct
10 Correct 491 ms 2644 KB Output is correct
11 Correct 397 ms 2628 KB Output is correct
12 Correct 765 ms 2812 KB Output is correct
13 Correct 457 ms 2624 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory 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 327 ms 1344 KB Output is correct
8 Correct 377 ms 1508 KB Output is correct
9 Correct 531 ms 2616 KB Output is correct
10 Correct 491 ms 2644 KB Output is correct
11 Correct 397 ms 2628 KB Output is correct
12 Correct 765 ms 2812 KB Output is correct
13 Correct 457 ms 2624 KB Output is correct
14 Correct 394 ms 1900 KB Output is correct
15 Correct 619 ms 1996 KB Output is correct
16 Correct 1191 ms 2864 KB Output is correct
17 Correct 1478 ms 3820 KB Output is correct
18 Correct 1493 ms 3588 KB Output is correct
19 Correct 1196 ms 3540 KB Output is correct
20 Correct 1494 ms 3680 KB Output is correct
21 Correct 1417 ms 3704 KB Output is correct
22 Correct 875 ms 3540 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory 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 327 ms 1344 KB Output is correct
8 Correct 377 ms 1508 KB Output is correct
9 Correct 531 ms 2616 KB Output is correct
10 Correct 491 ms 2644 KB Output is correct
11 Correct 397 ms 2628 KB Output is correct
12 Correct 765 ms 2812 KB Output is correct
13 Correct 457 ms 2624 KB Output is correct
14 Correct 394 ms 1900 KB Output is correct
15 Correct 619 ms 1996 KB Output is correct
16 Correct 1191 ms 2864 KB Output is correct
17 Correct 1478 ms 3820 KB Output is correct
18 Correct 1493 ms 3588 KB Output is correct
19 Correct 1196 ms 3540 KB Output is correct
20 Correct 1494 ms 3680 KB Output is correct
21 Correct 1417 ms 3704 KB Output is correct
22 Correct 875 ms 3540 KB Output is correct
23 Correct 5220 ms 7184 KB Output is correct
24 Correct 5330 ms 7184 KB Output is correct
25 Correct 4700 ms 7184 KB Output is correct
26 Correct 4660 ms 7188 KB Output is correct
27 Correct 6006 ms 7188 KB Output is correct
28 Correct 1634 ms 2380 KB Output is correct
29 Correct 1728 ms 2364 KB Output is correct
30 Correct 1639 ms 2260 KB Output is correct
31 Correct 1747 ms 2260 KB Output is correct
32 Correct 3400 ms 7188 KB Output is correct
33 Correct 2245 ms 7188 KB Output is correct
34 Correct 4511 ms 7188 KB Output is correct
35 Correct 2813 ms 7796 KB Output is correct
36 Correct 1445 ms 7184 KB Output is correct
37 Correct 6191 ms 7600 KB Output is correct
38 Correct 4470 ms 7184 KB Output is correct
39 Correct 5350 ms 7180 KB Output is correct
40 Correct 4400 ms 7188 KB Output is correct
41 Correct 6912 ms 7492 KB Output is correct
42 Correct 6786 ms 7460 KB Output is correct