oj.uz

Submission #116612

# Submission time Handle Problem Language Result Execution time Memory
116612 2019-06-13T05:25:59 Z dragonslayerit Dancing Elephants (IOI11_elephants) C++14
26 / 100
 9000 ms 3196 KB 
#include "elephants.h"
#include <vector>
#include <algorithm>

const int INF=1e9+7;

std::vector<int> xs;
std::vector<int> ys;
int l;

void init(int N, int L, int X[])
{
  l=L;
  for(int i=0;i<N;i++){
    xs.push_back(X[i]);
  }
  ys=xs;
}

int update(int i, int new_val)
{
  for(int& y:ys){
    if(y==xs[i]){
      y=new_val;
      break;
    }
  }
  xs[i]=new_val;
  //std::sort(ys.begin(),ys.end());
  
  for(int i=0;i<ys.size();i++){
    int tmp=ys[i];
    int j=i;
    while(j>0&&ys[j-1]>tmp){
      ys[j]=ys[j-1];
      j--;
    }
    ys[j]=tmp;
  }
  
  int far=-INF;
  int cnt=0;
  for(int x:ys){
    if(x>far){
      far=x+l;
      cnt++;
    }
  }
  return cnt;
}

Compilation message

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:31:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<ys.size();i++){
               ~^~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 3049 ms 1120 KB Output is correct
8 Correct 4257 ms 1164 KB Output is correct
9 Correct 5245 ms 3196 KB Output is correct
10 Correct 6523 ms 2980 KB Output is correct
11 Correct 6327 ms 2920 KB Output is correct
12 Execution timed out 9073 ms 3032 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 3049 ms 1120 KB Output is correct
8 Correct 4257 ms 1164 KB Output is correct
9 Correct 5245 ms 3196 KB Output is correct
10 Correct 6523 ms 2980 KB Output is correct
11 Correct 6327 ms 2920 KB Output is correct
12 Execution timed out 9073 ms 3032 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 3049 ms 1120 KB Output is correct
8 Correct 4257 ms 1164 KB Output is correct
9 Correct 5245 ms 3196 KB Output is correct
10 Correct 6523 ms 2980 KB Output is correct
11 Correct 6327 ms 2920 KB Output is correct
12 Execution timed out 9073 ms 3032 KB Time limit exceeded
13 Halted 0 ms 0 KB -