oj.uz

Submission #248594

# Submission time Handle Problem Language Result Execution time Memory
248594 2020-07-12T20:20:47 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>1000000){
    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;
}
/*
4 10
10 15 17 20
2 16
1 25
3 35
0 38
2 0
*/

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 2 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 2 ms 1920 KB Output is correct
7 Correct 2585 ms 2612 KB Output is correct
8 Correct 3698 ms 2628 KB Output is correct
9 Correct 5321 ms 2756 KB Output is correct
10 Correct 7542 ms 2760 KB Output is correct
11 Correct 7617 ms 2808 KB Output is correct
12 Execution timed out 9076 ms 2684 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 2 ms 1920 KB Output is correct
7 Correct 2585 ms 2612 KB Output is correct
8 Correct 3698 ms 2628 KB Output is correct
9 Correct 5321 ms 2756 KB Output is correct
10 Correct 7542 ms 2760 KB Output is correct
11 Correct 7617 ms 2808 KB Output is correct
12 Execution timed out 9076 ms 2684 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 2 ms 1920 KB Output is correct
7 Correct 2585 ms 2612 KB Output is correct
8 Correct 3698 ms 2628 KB Output is correct
9 Correct 5321 ms 2756 KB Output is correct
10 Correct 7542 ms 2760 KB Output is correct
11 Correct 7617 ms 2808 KB Output is correct
12 Execution timed out 9076 ms 2684 KB Time limit exceeded
13 Halted 0 ms 0 KB -