oj.uz

Submission #119731

# Submission time Handle Problem Language Result Execution time Memory
119731 2019-06-22T04:23:34 Z nvmdava Dancing Elephants (IOI11_elephants) C++17
26 / 100
 9000 ms 3448 KB 
#include "elephants.h"
#include <bits/stdc++.h>
#define ss second
#define ff first
using namespace std;

int n, l;
pair<int, int> a[50005];
int loc[50005];

void sorter(int id){
   while(id + 1 < n && a[id].ff > a[id + 1].ff){
      swap(a[id], a[id + 1]);
      swap(loc[a[id].ss], loc[a[id + 1].ss]);
      id++;
   }
   while(id && a[id].ff < a[id - 1].ff){
      swap(a[id], a[id - 1]);
      swap(loc[a[id].ss], loc[a[id - 1].ss]);
      id--;
   }
}

int count(){
   int lst = a[0].ff;
   int res = 1;
   for(int i = 1; i < n; i++){
      if(a[i].ff > lst + l){
         res++;
         lst = a[i].ff;
      }
   }
   return res;
}

void init(int N, int L, int X[]){
   n = N;
   l = L;
   for(int i = 0; i < N; i++){
      a[i].first = X[i];
      a[i].second = i;
   }
   sort(X, X + N);
   for(int i = 0; i < N; i++){
      loc[a[i].second] = i;
   }
}


int update(int i, int y){
   a[loc[i]].ff = y;
   sorter(loc[i]);
   return count();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 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 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 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 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 1819 ms 2116 KB Output is correct
8 Correct 2741 ms 2304 KB Output is correct
9 Correct 1467 ms 3448 KB Output is correct
10 Correct 8071 ms 3120 KB Output is correct
11 Correct 7741 ms 3148 KB Output is correct
12 Execution timed out 9030 ms 3192 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 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 1819 ms 2116 KB Output is correct
8 Correct 2741 ms 2304 KB Output is correct
9 Correct 1467 ms 3448 KB Output is correct
10 Correct 8071 ms 3120 KB Output is correct
11 Correct 7741 ms 3148 KB Output is correct
12 Execution timed out 9030 ms 3192 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 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 1819 ms 2116 KB Output is correct
8 Correct 2741 ms 2304 KB Output is correct
9 Correct 1467 ms 3448 KB Output is correct
10 Correct 8071 ms 3120 KB Output is correct
11 Correct 7741 ms 3148 KB Output is correct
12 Execution timed out 9030 ms 3192 KB Time limit exceeded
13 Halted 0 ms 0 KB -