oj.uz

Submission #754091

# Submission time Handle Problem Language Result Execution time Memory
754091 2023-06-06T16:54:56 Z nicksms Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 11876 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][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) {
  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]) 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

# 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 526 ms 1368 KB Output is correct
8 Correct 574 ms 1492 KB Output is correct
9 Correct 640 ms 2692 KB Output is correct
10 Correct 663 ms 2696 KB Output is correct
11 Correct 540 ms 2696 KB Output is correct
12 Correct 1014 ms 2700 KB Output is correct
13 Correct 656 ms 2764 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 526 ms 1368 KB Output is correct
8 Correct 574 ms 1492 KB Output is correct
9 Correct 640 ms 2692 KB Output is correct
10 Correct 663 ms 2696 KB Output is correct
11 Correct 540 ms 2696 KB Output is correct
12 Correct 1014 ms 2700 KB Output is correct
13 Correct 656 ms 2764 KB Output is correct
14 Correct 458 ms 1772 KB Output is correct
15 Correct 879 ms 1988 KB Output is correct
16 Correct 1584 ms 2924 KB Output is correct
17 Correct 1870 ms 3632 KB Output is correct
18 Correct 1896 ms 3632 KB Output is correct
19 Correct 1287 ms 3632 KB Output is correct
20 Correct 1801 ms 3540 KB Output is correct
21 Correct 1816 ms 3644 KB Output is correct
22 Correct 1293 ms 3636 KB Output is correct

Subtask #5
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 526 ms 1368 KB Output is correct
8 Correct 574 ms 1492 KB Output is correct
9 Correct 640 ms 2692 KB Output is correct
10 Correct 663 ms 2696 KB Output is correct
11 Correct 540 ms 2696 KB Output is correct
12 Correct 1014 ms 2700 KB Output is correct
13 Correct 656 ms 2764 KB Output is correct
14 Correct 458 ms 1772 KB Output is correct
15 Correct 879 ms 1988 KB Output is correct
16 Correct 1584 ms 2924 KB Output is correct
17 Correct 1870 ms 3632 KB Output is correct
18 Correct 1896 ms 3632 KB Output is correct
19 Correct 1287 ms 3632 KB Output is correct
20 Correct 1801 ms 3540 KB Output is correct
21 Correct 1816 ms 3644 KB Output is correct
22 Correct 1293 ms 3636 KB Output is correct
23 Correct 6395 ms 7360 KB Output is correct
24 Correct 6570 ms 7360 KB Output is correct
25 Correct 5402 ms 7616 KB Output is correct
26 Correct 6647 ms 7728 KB Output is correct
27 Correct 7007 ms 7612 KB Output is correct
28 Correct 2223 ms 2504 KB Output is correct
29 Correct 2024 ms 2508 KB Output is correct
30 Correct 2179 ms 2508 KB Output is correct
31 Correct 2048 ms 2504 KB Output is correct
32 Correct 4246 ms 7612 KB Output is correct
33 Correct 3183 ms 7628 KB Output is correct
34 Correct 5976 ms 7612 KB Output is correct
35 Correct 3226 ms 7620 KB Output is correct
36 Correct 1350 ms 7560 KB Output is correct
37 Correct 7703 ms 7612 KB Output is correct
38 Correct 6034 ms 7556 KB Output is correct
39 Correct 6358 ms 7568 KB Output is correct
40 Correct 5942 ms 7548 KB Output is correct
41 Correct 8473 ms 7536 KB Output is correct
42 Execution timed out 9048 ms 11876 KB Time limit exceeded
43 Halted 0 ms 0 KB -