oj.uz

Submission #754084

# Submission time Handle Problem Language Result Execution time Memory
754084 2023-06-06T16:23:14 Z nicksms Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 6916 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];
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) {
  // if (sz(buck[i])>=2*BS) cnt=2*BS;
  // 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 647 ms 1268 KB Output is correct
8 Correct 693 ms 1412 KB Output is correct
9 Correct 821 ms 2300 KB Output is correct
10 Correct 834 ms 2308 KB Output is correct
11 Correct 684 ms 2304 KB Output is correct
12 Correct 1191 ms 2432 KB Output is correct
13 Correct 836 ms 2304 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 647 ms 1268 KB Output is correct
8 Correct 693 ms 1412 KB Output is correct
9 Correct 821 ms 2300 KB Output is correct
10 Correct 834 ms 2308 KB Output is correct
11 Correct 684 ms 2304 KB Output is correct
12 Correct 1191 ms 2432 KB Output is correct
13 Correct 836 ms 2304 KB Output is correct
14 Correct 700 ms 1724 KB Output is correct
15 Correct 1090 ms 1880 KB Output is correct
16 Correct 1849 ms 2536 KB Output is correct
17 Correct 2154 ms 3248 KB Output is correct
18 Correct 2279 ms 3272 KB Output is correct
19 Correct 1484 ms 3084 KB Output is correct
20 Correct 2140 ms 3152 KB Output is correct
21 Correct 2060 ms 3168 KB Output is correct
22 Correct 1400 ms 3148 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 647 ms 1268 KB Output is correct
8 Correct 693 ms 1412 KB Output is correct
9 Correct 821 ms 2300 KB Output is correct
10 Correct 834 ms 2308 KB Output is correct
11 Correct 684 ms 2304 KB Output is correct
12 Correct 1191 ms 2432 KB Output is correct
13 Correct 836 ms 2304 KB Output is correct
14 Correct 700 ms 1724 KB Output is correct
15 Correct 1090 ms 1880 KB Output is correct
16 Correct 1849 ms 2536 KB Output is correct
17 Correct 2154 ms 3248 KB Output is correct
18 Correct 2279 ms 3272 KB Output is correct
19 Correct 1484 ms 3084 KB Output is correct
20 Correct 2140 ms 3152 KB Output is correct
21 Correct 2060 ms 3168 KB Output is correct
22 Correct 1400 ms 3148 KB Output is correct
23 Correct 6508 ms 6208 KB Output is correct
24 Correct 6586 ms 6316 KB Output is correct
25 Correct 5972 ms 6204 KB Output is correct
26 Correct 6489 ms 6216 KB Output is correct
27 Correct 6357 ms 6212 KB Output is correct
28 Correct 2119 ms 2248 KB Output is correct
29 Correct 2086 ms 2244 KB Output is correct
30 Correct 2146 ms 2244 KB Output is correct
31 Correct 2097 ms 2248 KB Output is correct
32 Correct 4478 ms 6208 KB Output is correct
33 Correct 3661 ms 6212 KB Output is correct
34 Correct 6161 ms 6212 KB Output is correct
35 Correct 3742 ms 6772 KB Output is correct
36 Correct 2209 ms 6208 KB Output is correct
37 Execution timed out 9024 ms 6916 KB Time limit exceeded
38 Halted 0 ms 0 KB -