oj.uz

Submission #1013916

# Submission time Handle Problem Language Result Execution time Memory
1013916 2024-07-04T08:08:05 Z boyliguanhan Dancing Elephants (IOI11_elephants) C++17
100 / 100
 1781 ms 22180 KB 
//after view the editorial
#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
int n,sz=500,arr[150100],cnt,num,len;
vector<int>buckets[310],need[310],lst[310];
void recalc(int id){
  if(buckets[id].empty())return;
  need[id].resize(buckets[id].size(),0);
  lst[id].resize(buckets[id].size(),0);
  int k=buckets[id].size()-1,l=buckets[id].back();
  while(k>=0&&buckets[id][k]>=l-len)  
    lst[id][k]=buckets[id][k]+len,need[id][k]=1,k--;
  int x=buckets[id].size()-1;
  while(k>=0){
    while(buckets[id][x-1]>buckets[id][k]+len)x--;
    lst[id][k]=lst[id][x];
    need[id][k]=need[id][x]+1;
    k--;
  }
}
void recons(){
  vector<int>thingys;
  for(int i=0;i<num;buckets[i++].clear())
    for(auto j:buckets[i])  
      thingys.push_back(j);
  int x=thingys.size();
  for(int i=0;i<num;recalc(i++))
    for(int j=i*sz;j<min(i*sz+sz,x);j++)
      buckets[i].push_back(thingys[j]);
}
int gedans(){
  int pew=-1,cnt=0;
  for(int i=0;i<num;i++){
    int x=upper_bound(all(buckets[i]),pew)-buckets[i].begin();
    if(x==buckets[i].size())continue;
    cnt+=need[i][x];
    pew=lst[i][x];
  }
  return cnt;
}
void init(int N, int L, int X[]) {
  n = N;
  len=L;
  for(int i=0;i<N;i++)
    buckets[0].push_back(arr[i]=X[i]);
  num=(n+sz-1)/sz;
  recons();
}
int update(int i, int y) {
  cnt++;
  int id=0;
  for(int x=0;x<num;x++)
    if(buckets[x].size()&&
      buckets[x].back()>=arr[i]){
      id=x; break;}
  buckets[id].erase(lower_bound(all(buckets[id]),arr[i]));
  recalc(id); arr[i]=y;
  id=num-1;
  for(int i=0;i<num;i++)
    if(buckets[i].size()&&y<=buckets[i].back()){
      id=i;break;}
  buckets[id].insert(lower_bound(all(buckets[id]),y),y);
  recalc(id);
  if(cnt==sz)
    cnt=0,recons();
  return gedans();
}

Compilation message

elephants.cpp: In function 'int gedans()':
elephants.cpp:37:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     if(x==buckets[i].size())continue;
      |        ~^~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8660 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8660 KB Output is correct
7 Correct 120 ms 10092 KB Output is correct
8 Correct 132 ms 10472 KB Output is correct
9 Correct 166 ms 13820 KB Output is correct
10 Correct 166 ms 13456 KB Output is correct
11 Correct 156 ms 13396 KB Output is correct
12 Correct 310 ms 14108 KB Output is correct
13 Correct 201 ms 13328 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8660 KB Output is correct
7 Correct 120 ms 10092 KB Output is correct
8 Correct 132 ms 10472 KB Output is correct
9 Correct 166 ms 13820 KB Output is correct
10 Correct 166 ms 13456 KB Output is correct
11 Correct 156 ms 13396 KB Output is correct
12 Correct 310 ms 14108 KB Output is correct
13 Correct 201 ms 13328 KB Output is correct
14 Correct 147 ms 10928 KB Output is correct
15 Correct 214 ms 11024 KB Output is correct
16 Correct 523 ms 14308 KB Output is correct
17 Correct 581 ms 15556 KB Output is correct
18 Correct 604 ms 15408 KB Output is correct
19 Correct 263 ms 14932 KB Output is correct
20 Correct 537 ms 15700 KB Output is correct
21 Correct 473 ms 15444 KB Output is correct
22 Correct 277 ms 14604 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8660 KB Output is correct
7 Correct 120 ms 10092 KB Output is correct
8 Correct 132 ms 10472 KB Output is correct
9 Correct 166 ms 13820 KB Output is correct
10 Correct 166 ms 13456 KB Output is correct
11 Correct 156 ms 13396 KB Output is correct
12 Correct 310 ms 14108 KB Output is correct
13 Correct 201 ms 13328 KB Output is correct
14 Correct 147 ms 10928 KB Output is correct
15 Correct 214 ms 11024 KB Output is correct
16 Correct 523 ms 14308 KB Output is correct
17 Correct 581 ms 15556 KB Output is correct
18 Correct 604 ms 15408 KB Output is correct
19 Correct 263 ms 14932 KB Output is correct
20 Correct 537 ms 15700 KB Output is correct
21 Correct 473 ms 15444 KB Output is correct
22 Correct 277 ms 14604 KB Output is correct
23 Correct 1372 ms 20600 KB Output is correct
24 Correct 1511 ms 20808 KB Output is correct
25 Correct 1008 ms 20340 KB Output is correct
26 Correct 1213 ms 19932 KB Output is correct
27 Correct 1168 ms 19728 KB Output is correct
28 Correct 403 ms 11608 KB Output is correct
29 Correct 410 ms 11608 KB Output is correct
30 Correct 401 ms 11608 KB Output is correct
31 Correct 411 ms 11828 KB Output is correct
32 Correct 1058 ms 19500 KB Output is correct
33 Correct 957 ms 18696 KB Output is correct
34 Correct 1006 ms 19572 KB Output is correct
35 Correct 919 ms 22180 KB Output is correct
36 Correct 906 ms 19356 KB Output is correct
37 Correct 1304 ms 21512 KB Output is correct
38 Correct 1091 ms 18848 KB Output is correct
39 Correct 992 ms 19664 KB Output is correct
40 Correct 1093 ms 18876 KB Output is correct
41 Correct 1737 ms 20628 KB Output is correct
42 Correct 1781 ms 20772 KB Output is correct