oj.uz

Submission #1096179

# Submission time Handle Problem Language Result Execution time Memory
1096179 2024-10-04T03:59:35 Z MtSaka Dancing Elephants (IOI11_elephants) C++17
50 / 100
 9000 ms 3676 KB 
#include "elephants.h"
#include"bits/stdc++.h"
#define overload(a,b,c,d,...) d
#define rep1(a) for(ll _=0;_<(ll)a;++_)
#define rep2(i,a) for(ll i=0;i<(ll)(a);++i)
#define rep3(i,a,b) for(ll i=(ll)(a);i<(ll)(b);++i)
#define rep(...) overload(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(i,a) for(ll i=(ll)(a)-1;i>=0;--i)
#define rrep2(i,a,b) for(ll i=(ll)(b)-1;i>=(ll)(a);--i)
#define rrep(...) overload(__VA_ARGS__,rrep2,rrep1)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll=long long;
using ull=unsigned long long;
using i128=__int128_t;
using ld=long double;
using vi=vector<int>;
using vl=vector<ll>;
template<typename T,typename U>inline bool chmin(T&a,const U&b){return (a>b?a=b,true:false);}
template<typename T,typename U>inline bool chmax(T&a,const U&b){return (a<b?a=b,true:false);}

int n;
vector<int>x;
vector<int>xs;
int l;
void init(int N, int L, int X[])
{
  n=N;
  x=vector<int>(X,X+N);
  xs=x;
  sort(all(xs));
  l=L;
}

int update(int id, int y)
{
  auto it=lower_bound(all(xs),x[id])-xs.begin();
  rep(i,it,n-1)xs[i]=xs[i+1];
  it=lower_bound(xs.begin(),xs.begin()+n-1,y)-xs.begin();
  rrep(i,it+1,n)xs[i]=xs[i-1];
  xs[it]=y;
  x[id]=y;
  int ans=1;
  int now=xs[0];
  rep(i,1,n){
    if(xs[i]-now>l){
      now=xs[i];
      ans++;
    }
  }
  return ans;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1242 ms 1848 KB Output is correct
8 Correct 2404 ms 2244 KB Output is correct
9 Correct 3382 ms 3164 KB Output is correct
10 Correct 3936 ms 2904 KB Output is correct
11 Correct 3987 ms 2908 KB Output is correct
12 Correct 6605 ms 3056 KB Output is correct
13 Correct 4384 ms 2652 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1242 ms 1848 KB Output is correct
8 Correct 2404 ms 2244 KB Output is correct
9 Correct 3382 ms 3164 KB Output is correct
10 Correct 3936 ms 2904 KB Output is correct
11 Correct 3987 ms 2908 KB Output is correct
12 Correct 6605 ms 3056 KB Output is correct
13 Correct 4384 ms 2652 KB Output is correct
14 Correct 2019 ms 2972 KB Output is correct
15 Correct 5260 ms 2948 KB Output is correct
16 Execution timed out 9054 ms 3676 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1242 ms 1848 KB Output is correct
8 Correct 2404 ms 2244 KB Output is correct
9 Correct 3382 ms 3164 KB Output is correct
10 Correct 3936 ms 2904 KB Output is correct
11 Correct 3987 ms 2908 KB Output is correct
12 Correct 6605 ms 3056 KB Output is correct
13 Correct 4384 ms 2652 KB Output is correct
14 Correct 2019 ms 2972 KB Output is correct
15 Correct 5260 ms 2948 KB Output is correct
16 Execution timed out 9054 ms 3676 KB Time limit exceeded
17 Halted 0 ms 0 KB -