oj.uz

Submission #754076

# Submission time Handle Problem Language Result Execution time Memory
754076 2023-06-06T16:13:16 Z nicksms Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 12200 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=387;
int pos[MAXN],j[MAXN],h[MAXN],ord[MAXN],w[MAXN];
vi buck[MAXN/BS + 5];
int cnt = 0;

int llt(const vi &v, int x) {
  if (!sz(v) || pos[v[0]] >= x) return -1;
  int l = 0,r=sz(v);
  while (r-l>1) {
    int m = (l+r)>>1;
    if (pos[v[m]] >= x) r=m;
    else l=m;
  }
  return l;
}

void fixbuck(int i) {
  // cerr << "fb: " << i << endl;
  // for (int x : buck[i]) cerr << x << " ";
  // cerr << endl;
  if (!sz(buck[i])) return;
  j[buck[i][0]]=pos[buck[i][0]]-l,h[buck[i][0]]=1;
  int lp = 0;
  for (int k = 1; k < sz(buck[i]); k++) {
    while (lp < sz(buck[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 : buck[i]) ord[cur++]=x;
    buck[i].resize(BS + 1);
  }
  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) buck[i/BS].resize(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].push_back(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));
  fixbuck(w[i]);
  pos[i]=y;
  w[i]=0;
  for (int k = 0; k <= (n-1)/BS; k++) {
    if (sz(buck[k]) && pos[buck[k][0]] < pos[i]) w[i]=k;
  }
  int ind = llt(buck[w[i]],pos[i])+1;
  buck[w[i]].insert(buck[w[i]].begin()+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(buck[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 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 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 1 ms 340 KB Output is correct
7 Correct 545 ms 2188 KB Output is correct
8 Correct 617 ms 2444 KB Output is correct
9 Correct 870 ms 3920 KB Output is correct
10 Correct 741 ms 3708 KB Output is correct
11 Correct 623 ms 3644 KB Output is correct
12 Correct 1168 ms 3808 KB Output is correct
13 Correct 757 ms 3492 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 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 545 ms 2188 KB Output is correct
8 Correct 617 ms 2444 KB Output is correct
9 Correct 870 ms 3920 KB Output is correct
10 Correct 741 ms 3708 KB Output is correct
11 Correct 623 ms 3644 KB Output is correct
12 Correct 1168 ms 3808 KB Output is correct
13 Correct 757 ms 3492 KB Output is correct
14 Correct 635 ms 3360 KB Output is correct
15 Correct 1018 ms 3252 KB Output is correct
16 Correct 1907 ms 4404 KB Output is correct
17 Correct 2264 ms 5324 KB Output is correct
18 Correct 2275 ms 5140 KB Output is correct
19 Correct 1541 ms 5340 KB Output is correct
20 Correct 2208 ms 5212 KB Output is correct
21 Correct 2128 ms 5176 KB Output is correct
22 Correct 1462 ms 4772 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 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 545 ms 2188 KB Output is correct
8 Correct 617 ms 2444 KB Output is correct
9 Correct 870 ms 3920 KB Output is correct
10 Correct 741 ms 3708 KB Output is correct
11 Correct 623 ms 3644 KB Output is correct
12 Correct 1168 ms 3808 KB Output is correct
13 Correct 757 ms 3492 KB Output is correct
14 Correct 635 ms 3360 KB Output is correct
15 Correct 1018 ms 3252 KB Output is correct
16 Correct 1907 ms 4404 KB Output is correct
17 Correct 2264 ms 5324 KB Output is correct
18 Correct 2275 ms 5140 KB Output is correct
19 Correct 1541 ms 5340 KB Output is correct
20 Correct 2208 ms 5212 KB Output is correct
21 Correct 2128 ms 5176 KB Output is correct
22 Correct 1462 ms 4772 KB Output is correct
23 Correct 8093 ms 11408 KB Output is correct
24 Correct 7477 ms 11400 KB Output is correct
25 Correct 7825 ms 11404 KB Output is correct
26 Correct 7365 ms 11468 KB Output is correct
27 Correct 7506 ms 11260 KB Output is correct
28 Correct 1744 ms 5164 KB Output is correct
29 Correct 1721 ms 5280 KB Output is correct
30 Correct 1748 ms 5156 KB Output is correct
31 Correct 1692 ms 5164 KB Output is correct
32 Correct 5368 ms 10840 KB Output is correct
33 Correct 3919 ms 10164 KB Output is correct
34 Correct 7199 ms 11044 KB Output is correct
35 Correct 4139 ms 12200 KB Output is correct
36 Correct 1964 ms 10828 KB Output is correct
37 Execution timed out 9013 ms 12140 KB Time limit exceeded
38 Halted 0 ms 0 KB -