oj.uz

Submission #1025044

# Submission time Handle Problem Language Result Execution time Memory
1025044 2024-07-16T14:44:05 Z mindiyak Dancing Elephants (IOI11_elephants) C++14
50 / 100
 9000 ms 5332 KB 
#include "elephants.h"
#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
#include <string>
#include <iostream>
#include <cmath>
#include <numeric>
#include <set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<int, int> pl;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
#define FOR(i, a, b) for (int i = a; i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define FORd(i, a, b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i, a) for (int i = (a)-1; i >= 0; i--)
#define trav(a, x) for (auto &a : x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define len(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define F first
#define nl endl
#define S second
#define lb lower_bound
#define ub upper_bound
#define aint(x) x.begin(), x.end()
#define raint(x) x.rbegin(), x.rend()
#define ins insert
const int MOD = 1000000007;
 
int N,L;
int arr[1000000];
int idx[1000000];
 
void init(int n, int l, int X[])
{
  N=n;L=l;
  vpi arr2;
  FOR(i,0,N){
    arr2.pb({X[i],i});
  }
  FOR(i,0,N){
    arr[i] = arr2[i].F;
    idx[i] = arr2[i].S;
  }
}
 
int update(int p, int y)
{
  int pos = 0;
  FOR(i,0,N){
    if(idx[i] == p){
      pos = i;
      break;
    }
  }

  arr[pos] = y;

  while (pos+1 < N && arr[pos] > arr[pos+1]) {
		swap(arr[pos], arr[pos+1]);
		swap(idx[pos], idx[pos+1]);
		pos++;
	}
	while (pos-1 >= 0 && arr[pos] < arr[pos-1]) {
		swap(arr[pos], arr[pos-1]);
		swap(idx[pos], idx[pos-1]);
		pos--;
	}

  int ans = 0,start = -1;
  FOR(i,0,N){
    if(ans == 0 || arr[i] > start+L){
      ans ++;
      start = arr[i];
    }
  }

  return ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 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 1 ms 2392 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 600 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 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 600 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 480 ms 2252 KB Output is correct
8 Correct 696 ms 4440 KB Output is correct
9 Correct 1255 ms 3540 KB Output is correct
10 Correct 4667 ms 5332 KB Output is correct
11 Correct 4725 ms 3280 KB Output is correct
12 Correct 5196 ms 5332 KB Output is correct
13 Correct 4748 ms 3284 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 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 600 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 480 ms 2252 KB Output is correct
8 Correct 696 ms 4440 KB Output is correct
9 Correct 1255 ms 3540 KB Output is correct
10 Correct 4667 ms 5332 KB Output is correct
11 Correct 4725 ms 3280 KB Output is correct
12 Correct 5196 ms 5332 KB Output is correct
13 Correct 4748 ms 3284 KB Output is correct
14 Correct 1389 ms 3284 KB Output is correct
15 Correct 1257 ms 3288 KB Output is correct
16 Execution timed out 9059 ms 4052 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 2392 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 600 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 480 ms 2252 KB Output is correct
8 Correct 696 ms 4440 KB Output is correct
9 Correct 1255 ms 3540 KB Output is correct
10 Correct 4667 ms 5332 KB Output is correct
11 Correct 4725 ms 3280 KB Output is correct
12 Correct 5196 ms 5332 KB Output is correct
13 Correct 4748 ms 3284 KB Output is correct
14 Correct 1389 ms 3284 KB Output is correct
15 Correct 1257 ms 3288 KB Output is correct
16 Execution timed out 9059 ms 4052 KB Time limit exceeded
17 Halted 0 ms 0 KB -