oj.uz

Submission #754120

# Submission time Handle Problem Language Result Execution time Memory
754120 2023-06-06T18:04:17 Z nicksms Dancing Elephants (IOI11_elephants) C++17
100 / 100
 5250 ms 7236 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*800) 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 0 ms 340 KB Output is correct
3 Correct 1 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 0 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 340 KB Output is correct
6 Correct 0 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 0 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 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 438 ms 1312 KB Output is correct
8 Correct 460 ms 1492 KB Output is correct
9 Correct 525 ms 2504 KB Output is correct
10 Correct 463 ms 2504 KB Output is correct
11 Correct 412 ms 2504 KB Output is correct
12 Correct 811 ms 2660 KB Output is correct
13 Correct 414 ms 2636 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 0 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 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 438 ms 1312 KB Output is correct
8 Correct 460 ms 1492 KB Output is correct
9 Correct 525 ms 2504 KB Output is correct
10 Correct 463 ms 2504 KB Output is correct
11 Correct 412 ms 2504 KB Output is correct
12 Correct 811 ms 2660 KB Output is correct
13 Correct 414 ms 2636 KB Output is correct
14 Correct 441 ms 1856 KB Output is correct
15 Correct 739 ms 1984 KB Output is correct
16 Correct 1382 ms 2740 KB Output is correct
17 Correct 1478 ms 3528 KB Output is correct
18 Correct 1512 ms 3424 KB Output is correct
19 Correct 1002 ms 3372 KB Output is correct
20 Correct 1458 ms 3500 KB Output is correct
21 Correct 1384 ms 3652 KB Output is correct
22 Correct 743 ms 3372 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 0 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 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 438 ms 1312 KB Output is correct
8 Correct 460 ms 1492 KB Output is correct
9 Correct 525 ms 2504 KB Output is correct
10 Correct 463 ms 2504 KB Output is correct
11 Correct 412 ms 2504 KB Output is correct
12 Correct 811 ms 2660 KB Output is correct
13 Correct 414 ms 2636 KB Output is correct
14 Correct 441 ms 1856 KB Output is correct
15 Correct 739 ms 1984 KB Output is correct
16 Correct 1382 ms 2740 KB Output is correct
17 Correct 1478 ms 3528 KB Output is correct
18 Correct 1512 ms 3424 KB Output is correct
19 Correct 1002 ms 3372 KB Output is correct
20 Correct 1458 ms 3500 KB Output is correct
21 Correct 1384 ms 3652 KB Output is correct
22 Correct 743 ms 3372 KB Output is correct
23 Correct 3714 ms 6832 KB Output is correct
24 Correct 4024 ms 6848 KB Output is correct
25 Correct 3383 ms 6824 KB Output is correct
26 Correct 3404 ms 6868 KB Output is correct
27 Correct 4733 ms 6824 KB Output is correct
28 Correct 1828 ms 2240 KB Output is correct
29 Correct 1789 ms 2240 KB Output is correct
30 Correct 1790 ms 2272 KB Output is correct
31 Correct 1820 ms 2244 KB Output is correct
32 Correct 2997 ms 6824 KB Output is correct
33 Correct 1830 ms 6928 KB Output is correct
34 Correct 3233 ms 6824 KB Output is correct
35 Correct 2376 ms 7236 KB Output is correct
36 Correct 1665 ms 6824 KB Output is correct
37 Correct 4540 ms 7128 KB Output is correct
38 Correct 3246 ms 6820 KB Output is correct
39 Correct 3727 ms 6824 KB Output is correct
40 Correct 3190 ms 6920 KB Output is correct
41 Correct 5250 ms 7076 KB Output is correct
42 Correct 5213 ms 7084 KB Output is correct