oj.uz

Submission #788502

# Submission time Handle Problem Language Result Execution time Memory
788502 2023-07-20T09:48:38 Z I_Love_EliskaM_ Dancing Elephants (IOI11_elephants) C++14
100 / 100
 2853 ms 14780 KB 
#include "elephants.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0; i<n; ++i)
#define pb push_back
#define all(x) x.begin(),x.end()
#define pi pair<int,int>
#define f first
#define s second
mt19937 rng(998244353);

const int N=2e5+5;
int a[N];
int b[N];
 
const int K=400;
int block[K][2*K];
int nxt[K][2*K];
int val[K][2*K];
int sz[K];
pi go[K][2*K];

int n,len;


void make(int i) {
  int R=0;
  for (int L=0; L<sz[i]; ++L) {
    while (R<sz[i] && block[i][R]-block[i][L]<=len) ++R;
    nxt[i][L]=R;
    val[i][L]=block[i][L]+len;
  }

  for (int j=sz[i]-1; j>=0; --j) {
    if (nxt[i][j]==sz[i]) {
      go[i][j]={1,val[i][j]};
    } else {
      go[i][j]={go[i][nxt[i][j]].f+1,go[i][nxt[i][j]].s};
    }
  }
}

void build() {
  n=0;
  forn(i,K) {
    forn(j,sz[i]) b[n++]=block[i][j];
  }
  for(int l=0; l<n; l+=K) {
    int r=min(l+K,n);
    sz[l/K]=r-l;
    for(int i=l; i<r; ++i) {
      block[l/K][i-l]=b[i];
    }

    int i=l/K;
    make(i); 
  }
}

void init(int _n, int _l, int x[]) {
  n=_n; len=_l;
  forn(i,n) a[i]=x[i];
  forn(i,n) b[i]=a[i];
  sort(b,b+n);

  for(int l=0; l<n; l+=K) {
    int r=min(l+K,n);
    sz[l/K]=r-l;
    for(int i=l; i<r; ++i) {
      block[l/K][i-l]=b[i];
    }
  }

  build();

}

void rem(int i, int x) {
  forn(j,sz[i]) {
    if (block[i][j]<x) continue;
    block[i][j]=block[i][j+1];
  }
  --sz[i];
  make(i);
}
void del(int x) {
  for (int i=0; i<K; ++i) {
    if (x<=block[i][sz[i]-1]) {
      rem(i,x);
      break;
    }
  }
}

void insert(int i, int x) {
  int z=1;
  int t=x;
  forn(j,sz[i]) {
    if (block[i][j]<x) continue;
    swap(t,block[i][j]);
  }
  block[i][sz[i]]=t;
  ++sz[i];
  make(i);
}
void add(int x) {
  for (int i=0; i<K; ++i) {
    if (x<=block[i][sz[i]-1]) {
      insert(i,x);
      break;
    }
    if (i==(n-1)/K) {
      insert(i,x);
      break;
    }
  }
}

int Q=0;
int update(int ind, int x) {
  
  del(a[ind]);
  a[ind]=x;
  add(a[ind]);

  ++Q;
  if (Q==K) {
    Q=0;
    build();
  }

  //forn(i,n) {
  //  if (!sz[i]) break;
  //  forn(j,sz[i]) cout<<block[i][j]<<' '; cout<<'\n';
  //  forn(j,sz[i]) cout<<nxt[i][j]<<' '; cout<<'\n';
  //  forn(j,sz[i]) cout<<val[i][j]<<' '; cout<<'\n';
  //  forn(j,sz[i]) cout<<go[i][j].f<<','<<go[i][j].s<<"  "; cout<<'\n';
  //}

  int i=0, j=0, pos=block[0][0];
  int ans=0;

  for (;sz[i];) {
    auto it = go[i][j];
    ans += it.f;
    pos = it.s;

    while (sz[i] && block[i][sz[i]-1]<=pos) ++i;
    if (!sz[i]) break;
    int l=0, r=sz[i]-1;
    while (l<r) {
      int m=(l+r)>>1;
      if (block[i][m]<=pos) l=m+1;
      else r=m;
    }
    j=r;
  }
  return ans;

}

Compilation message

elephants.cpp: In function 'void insert(int, int)':
elephants.cpp:98:7: warning: unused variable 'z' [-Wunused-variable]
   98 |   int z=1;
      |       ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 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 320 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 324 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 320 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 324 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 319 ms 2480 KB Output is correct
8 Correct 340 ms 2772 KB Output is correct
9 Correct 329 ms 5028 KB Output is correct
10 Correct 324 ms 4908 KB Output is correct
11 Correct 273 ms 4680 KB Output is correct
12 Correct 528 ms 4908 KB Output is correct
13 Correct 282 ms 4604 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 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 324 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 319 ms 2480 KB Output is correct
8 Correct 340 ms 2772 KB Output is correct
9 Correct 329 ms 5028 KB Output is correct
10 Correct 324 ms 4908 KB Output is correct
11 Correct 273 ms 4680 KB Output is correct
12 Correct 528 ms 4908 KB Output is correct
13 Correct 282 ms 4604 KB Output is correct
14 Correct 314 ms 3580 KB Output is correct
15 Correct 520 ms 3772 KB Output is correct
16 Correct 863 ms 5512 KB Output is correct
17 Correct 908 ms 6756 KB Output is correct
18 Correct 915 ms 6732 KB Output is correct
19 Correct 449 ms 6900 KB Output is correct
20 Correct 892 ms 6760 KB Output is correct
21 Correct 839 ms 6728 KB Output is correct
22 Correct 459 ms 6328 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 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 324 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 319 ms 2480 KB Output is correct
8 Correct 340 ms 2772 KB Output is correct
9 Correct 329 ms 5028 KB Output is correct
10 Correct 324 ms 4908 KB Output is correct
11 Correct 273 ms 4680 KB Output is correct
12 Correct 528 ms 4908 KB Output is correct
13 Correct 282 ms 4604 KB Output is correct
14 Correct 314 ms 3580 KB Output is correct
15 Correct 520 ms 3772 KB Output is correct
16 Correct 863 ms 5512 KB Output is correct
17 Correct 908 ms 6756 KB Output is correct
18 Correct 915 ms 6732 KB Output is correct
19 Correct 449 ms 6900 KB Output is correct
20 Correct 892 ms 6760 KB Output is correct
21 Correct 839 ms 6728 KB Output is correct
22 Correct 459 ms 6328 KB Output is correct
23 Correct 2273 ms 14760 KB Output is correct
24 Correct 2464 ms 14764 KB Output is correct
25 Correct 1634 ms 14780 KB Output is correct
26 Correct 2012 ms 14764 KB Output is correct
27 Correct 1894 ms 14540 KB Output is correct
28 Correct 1167 ms 5260 KB Output is correct
29 Correct 1108 ms 5268 KB Output is correct
30 Correct 1156 ms 5264 KB Output is correct
31 Correct 1124 ms 5260 KB Output is correct
32 Correct 1329 ms 14200 KB Output is correct
33 Correct 1342 ms 13528 KB Output is correct
34 Correct 1633 ms 14408 KB Output is correct
35 Correct 993 ms 14696 KB Output is correct
36 Correct 399 ms 14176 KB Output is correct
37 Correct 2278 ms 14592 KB Output is correct
38 Correct 1526 ms 13408 KB Output is correct
39 Correct 1453 ms 14432 KB Output is correct
40 Correct 1468 ms 13444 KB Output is correct
41 Correct 2824 ms 14184 KB Output is correct
42 Correct 2853 ms 14416 KB Output is correct