oj.uz

Submission #248595

# Submission time Handle Problem Language Result Execution time Memory
248595 2020-07-12T20:22:08 Z davi_bart Dancing Elephants (IOI11_elephants) C++14
26 / 100
 9000 ms 2808 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "elephants.h"
using namespace std;
typedef long long ll;
//#define int ll
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n;
vector<int> v(200010);
vector<int> p(200010);
int dim;
void init(int N, int L, int X[]){
  n=N;
  v.resize(N);
  p.resize(N);
  for(int i=0;i<N;i++){
      p[i]=v[i]=X[i];
  }
  dim=L;
}
int update(int i,int y){
  p.erase(lower_bound(p.begin(),p.end(),v[i]));
  p.insert(upper_bound(p.begin(),p.end(),y),y);
  v[i]=y;
  int pos=p[0];
  int tot=1;
  if(dim>10000){
    while(1){
      int w=upper_bound(p.begin(),p.end(),pos+dim)-p.begin();
      if(w==p.size())break;
      tot++;
      pos=p[w];
    }
  }else{
    for(int x:p){
      if(x-pos<=dim)continue;
      tot++;
      pos=x;
    }
  }
  return tot;
}

Compilation message

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:30:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(w==p.size())break;
          ~^~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1920 KB Output is correct
2 Correct 1 ms 1920 KB Output is correct
3 Correct 1 ms 1920 KB Output is correct
4 Correct 1 ms 1920 KB Output is correct
5 Correct 1 ms 1920 KB Output is correct
6 Correct 1 ms 1920 KB Output is correct
7 Correct 2584 ms 2612 KB Output is correct
8 Correct 3743 ms 2628 KB Output is correct
9 Correct 5261 ms 2808 KB Output is correct
10 Correct 7510 ms 2808 KB Output is correct
11 Correct 7547 ms 2808 KB Output is correct
12 Execution timed out 9090 ms 2688 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1920 KB Output is correct
2 Correct 1 ms 1920 KB Output is correct
3 Correct 1 ms 1920 KB Output is correct
4 Correct 1 ms 1920 KB Output is correct
5 Correct 1 ms 1920 KB Output is correct
6 Correct 1 ms 1920 KB Output is correct
7 Correct 2584 ms 2612 KB Output is correct
8 Correct 3743 ms 2628 KB Output is correct
9 Correct 5261 ms 2808 KB Output is correct
10 Correct 7510 ms 2808 KB Output is correct
11 Correct 7547 ms 2808 KB Output is correct
12 Execution timed out 9090 ms 2688 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1920 KB Output is correct
2 Correct 1 ms 1920 KB Output is correct
3 Correct 1 ms 1920 KB Output is correct
4 Correct 1 ms 1920 KB Output is correct
5 Correct 1 ms 1920 KB Output is correct
6 Correct 1 ms 1920 KB Output is correct
7 Correct 2584 ms 2612 KB Output is correct
8 Correct 3743 ms 2628 KB Output is correct
9 Correct 5261 ms 2808 KB Output is correct
10 Correct 7510 ms 2808 KB Output is correct
11 Correct 7547 ms 2808 KB Output is correct
12 Execution timed out 9090 ms 2688 KB Time limit exceeded
13 Halted 0 ms 0 KB -