oj.uz

Submission #781714

# Submission time Handle Problem Language Result Execution time Memory
781714 2023-07-13T10:20:13 Z I_Love_EliskaM_ Dancing Elephants (IOI11_elephants) C++14
50 / 100
 9000 ms 2252 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0; i<n; ++i)
#define pb push_back
#define all(x) x.begin(),x.end()
mt19937 rng(998244353);

const int N=50005;
int pos[N],ind[N],a[N];

int n,l;
void init(int _n, int _l, int x[]) {
  n=_n; l=_l; if (n>50000) exit(0);
  forn(i,n) a[i]=x[i];
  forn(i,n) pos[i]=ind[i]=i;
}
int update(int i, int x) {
  i=pos[i];
  if (x>a[i]) {
    while (i<n-1 && a[i+1]<x) {
      swap(ind[i],ind[i+1]);
      pos[ind[i]]=i;
      swap(a[i],a[i+1]);
      ++i;
    }
    a[i]=x;
    pos[ind[i]]=i;
  } else {
    while (i && a[i-1]>x) {
      swap(ind[i],ind[i-1]);
      pos[ind[i]]=i;
      swap(a[i],a[i-1]);
      --i;
    }
    a[i]=x;
    pos[ind[i]]=i;
  }
  
  int ans=0;
  int r=-1;
  forn(i,n) {
    if (a[i]>r) {
      r=a[i]+l;
      ++ans;
    }
  }
  return ans;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1051 ms 1488 KB Output is correct
8 Correct 2029 ms 1568 KB Output is correct
9 Correct 1467 ms 2072 KB Output is correct
10 Correct 7291 ms 2068 KB Output is correct
11 Correct 7504 ms 2068 KB Output is correct
12 Correct 7223 ms 2112 KB Output is correct
13 Correct 7509 ms 2076 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1051 ms 1488 KB Output is correct
8 Correct 2029 ms 1568 KB Output is correct
9 Correct 1467 ms 2072 KB Output is correct
10 Correct 7291 ms 2068 KB Output is correct
11 Correct 7504 ms 2068 KB Output is correct
12 Correct 7223 ms 2112 KB Output is correct
13 Correct 7509 ms 2076 KB Output is correct
14 Correct 1789 ms 1808 KB Output is correct
15 Correct 4180 ms 1964 KB Output is correct
16 Execution timed out 9023 ms 2252 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1051 ms 1488 KB Output is correct
8 Correct 2029 ms 1568 KB Output is correct
9 Correct 1467 ms 2072 KB Output is correct
10 Correct 7291 ms 2068 KB Output is correct
11 Correct 7504 ms 2068 KB Output is correct
12 Correct 7223 ms 2112 KB Output is correct
13 Correct 7509 ms 2076 KB Output is correct
14 Correct 1789 ms 1808 KB Output is correct
15 Correct 4180 ms 1964 KB Output is correct
16 Execution timed out 9023 ms 2252 KB Time limit exceeded
17 Halted 0 ms 0 KB -