oj.uz

Submission #754080

# Submission time Handle Problem Language Result Execution time Memory
754080 2023-06-06T16:19:43 Z nicksms Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 11264 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 320 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 320 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 648 ms 1420 KB Output is correct
8 Correct 688 ms 1552 KB Output is correct
9 Correct 740 ms 2456 KB Output is correct
10 Correct 826 ms 2448 KB Output is correct
11 Correct 694 ms 2452 KB Output is correct
12 Correct 1182 ms 2516 KB Output is correct
13 Correct 832 ms 2456 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 320 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 648 ms 1420 KB Output is correct
8 Correct 688 ms 1552 KB Output is correct
9 Correct 740 ms 2456 KB Output is correct
10 Correct 826 ms 2448 KB Output is correct
11 Correct 694 ms 2452 KB Output is correct
12 Correct 1182 ms 2516 KB Output is correct
13 Correct 832 ms 2456 KB Output is correct
14 Correct 662 ms 2060 KB Output is correct
15 Correct 1058 ms 2148 KB Output is correct
16 Correct 1752 ms 2952 KB Output is correct
17 Correct 1991 ms 3668 KB Output is correct
18 Correct 2170 ms 3300 KB Output is correct
19 Correct 1388 ms 3252 KB Output is correct
20 Correct 2081 ms 3660 KB Output is correct
21 Correct 1982 ms 3352 KB Output is correct
22 Correct 1421 ms 3240 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 320 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 648 ms 1420 KB Output is correct
8 Correct 688 ms 1552 KB Output is correct
9 Correct 740 ms 2456 KB Output is correct
10 Correct 826 ms 2448 KB Output is correct
11 Correct 694 ms 2452 KB Output is correct
12 Correct 1182 ms 2516 KB Output is correct
13 Correct 832 ms 2456 KB Output is correct
14 Correct 662 ms 2060 KB Output is correct
15 Correct 1058 ms 2148 KB Output is correct
16 Correct 1752 ms 2952 KB Output is correct
17 Correct 1991 ms 3668 KB Output is correct
18 Correct 2170 ms 3300 KB Output is correct
19 Correct 1388 ms 3252 KB Output is correct
20 Correct 2081 ms 3660 KB Output is correct
21 Correct 1982 ms 3352 KB Output is correct
22 Correct 1421 ms 3240 KB Output is correct
23 Correct 5757 ms 6412 KB Output is correct
24 Correct 5965 ms 6440 KB Output is correct
25 Correct 5627 ms 6204 KB Output is correct
26 Correct 6858 ms 6216 KB Output is correct
27 Correct 6740 ms 6216 KB Output is correct
28 Correct 2582 ms 2248 KB Output is correct
29 Correct 2489 ms 2252 KB Output is correct
30 Correct 2563 ms 2372 KB Output is correct
31 Correct 2477 ms 2248 KB Output is correct
32 Correct 4645 ms 6220 KB Output is correct
33 Correct 3594 ms 6272 KB Output is correct
34 Correct 6091 ms 6208 KB Output is correct
35 Correct 3769 ms 6708 KB Output is correct
36 Correct 2227 ms 6208 KB Output is correct
37 Correct 8559 ms 6756 KB Output is correct
38 Correct 6635 ms 9872 KB Output is correct
39 Correct 6646 ms 10908 KB Output is correct
40 Correct 6622 ms 9904 KB Output is correct
41 Execution timed out 9010 ms 11264 KB Time limit exceeded
42 Halted 0 ms 0 KB -