oj.uz

Submission #1013883

# Submission time Handle Problem Language Result Execution time Memory
1013883 2024-07-04T07:33:17 Z vjudge1 Dancing Elephants (IOI11_elephants) C++17
26 / 100
 15 ms 17936 KB 
#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
int n,sz=400,arr[150100],cnt,num,len;
vector<int>buckets[1000],need[1000],lst[1000];
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;
  while(k>=0){
    int x=upper_bound(all(buckets[id]),buckets[id][k]+len)-buckets[id].begin();
    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);
  for(int i=0;i<num;recalc(i++))
    for(int j=i*sz;j<min(i*sz+sz,n);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 i=0;i<num;i++)
    if(buckets[i].size()&&
      buckets[i].back()>=arr[i]){
      id=i; 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][0]){
      id=max(0,i-1);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:34:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     if(x==buckets[i].size())continue;
      |        ~^~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8548 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Runtime error 15 ms 17936 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8548 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Runtime error 15 ms 17936 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8548 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Runtime error 15 ms 17936 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -