oj.uz

Submission #754095

# Submission time Handle Problem Language Result Execution time Memory
754095 2023-06-06T16:58:33 Z nicksms Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 7616 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=420;
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 1 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 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 312 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 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 468 ms 1712 KB Output is correct
8 Correct 514 ms 1796 KB Output is correct
9 Correct 646 ms 2912 KB Output is correct
10 Correct 635 ms 2948 KB Output is correct
11 Correct 525 ms 2948 KB Output is correct
12 Correct 945 ms 2952 KB Output is correct
13 Correct 680 ms 2948 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 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 468 ms 1712 KB Output is correct
8 Correct 514 ms 1796 KB Output is correct
9 Correct 646 ms 2912 KB Output is correct
10 Correct 635 ms 2948 KB Output is correct
11 Correct 525 ms 2948 KB Output is correct
12 Correct 945 ms 2952 KB Output is correct
13 Correct 680 ms 2948 KB Output is correct
14 Correct 453 ms 1976 KB Output is correct
15 Correct 817 ms 2360 KB Output is correct
16 Correct 1557 ms 3180 KB Output is correct
17 Correct 1932 ms 3880 KB Output is correct
18 Correct 1953 ms 3876 KB Output is correct
19 Correct 1254 ms 3880 KB Output is correct
20 Correct 1939 ms 3880 KB Output is correct
21 Correct 1856 ms 3880 KB Output is correct
22 Correct 1265 ms 3880 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 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 312 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 468 ms 1712 KB Output is correct
8 Correct 514 ms 1796 KB Output is correct
9 Correct 646 ms 2912 KB Output is correct
10 Correct 635 ms 2948 KB Output is correct
11 Correct 525 ms 2948 KB Output is correct
12 Correct 945 ms 2952 KB Output is correct
13 Correct 680 ms 2948 KB Output is correct
14 Correct 453 ms 1976 KB Output is correct
15 Correct 817 ms 2360 KB Output is correct
16 Correct 1557 ms 3180 KB Output is correct
17 Correct 1932 ms 3880 KB Output is correct
18 Correct 1953 ms 3876 KB Output is correct
19 Correct 1254 ms 3880 KB Output is correct
20 Correct 1939 ms 3880 KB Output is correct
21 Correct 1856 ms 3880 KB Output is correct
22 Correct 1265 ms 3880 KB Output is correct
23 Correct 6285 ms 7616 KB Output is correct
24 Correct 6361 ms 7616 KB Output is correct
25 Correct 5748 ms 7360 KB Output is correct
26 Correct 6471 ms 7364 KB Output is correct
27 Correct 6883 ms 7360 KB Output is correct
28 Correct 1892 ms 2248 KB Output is correct
29 Correct 1804 ms 2248 KB Output is correct
30 Correct 1865 ms 2244 KB Output is correct
31 Correct 1816 ms 2244 KB Output is correct
32 Correct 4236 ms 7364 KB Output is correct
33 Correct 3183 ms 7364 KB Output is correct
34 Correct 6556 ms 7364 KB Output is correct
35 Correct 3390 ms 7364 KB Output is correct
36 Correct 1417 ms 7356 KB Output is correct
37 Correct 8393 ms 7360 KB Output is correct
38 Correct 6951 ms 7364 KB Output is correct
39 Correct 6162 ms 7360 KB Output is correct
40 Correct 6630 ms 7372 KB Output is correct
41 Execution timed out 9026 ms 7356 KB Time limit exceeded
42 Halted 0 ms 0 KB -