oj.uz

Submission #993851

# Submission time Handle Problem Language Result Execution time Memory
993851 2024-06-06T14:18:41 Z midi Dancing Elephants (IOI11_elephants) C++17
50 / 100
 9000 ms 12240 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define vc vector
typedef vc<ll> vcll;
typedef vc<bool> vcb;
#define pr pair
typedef pr<ll, ll> prll;
typedef set<ll> setll;
typedef map<ll,ll> mapll;
#define uset unordered_set
typedef uset<ll> usetll;
#define umap unordered_map
typedef umap<ll,ll> umapll;

#define f0r(i,a,n) for ((i)=(a); (i)<=(n); (i)++)
#define r0f(i,n,a) for ((i)=(n); (i)>=(a); (i)--)

#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define mp make_pair
#define fi first
#define se second
#define sz size
#define all(x) (x).begin(), (x).end()
#define all0(x, n) (x).begin(), (x).begin()+n
#define all1(x, n) (x).begin()+1, (x).begin()+n+1
#define allrev(x) (x).rbegin(), (x).rend()
#define in(v, s) ((s).find((v)) != (s).end())
#define GCD(x, y) __gcd(abs((x)), abs((y)))

#define INF (LLONG_MAX>>3ll)
#define MOD (1'000'000'007ll)

#define mxN (150'010ll)

inline void maxa(ll &a, ll b) { if (a<b) a=b; }
inline void mina(ll &a, ll b) { if (a>b) a=b; }

inline void print (vcll &a, ll n=-1, string name="")
{
	cout << name << ": ";
	if (n==-1) for (ll x:a) printf("%lli ", x);
	else
	{
		ll i;
		f0r(i,1,n) printf("%lli ", a[i]);
	}
	printf("\n");
}

ll n, L;
vcll ar(mxN);
vcll nums;

inline void ins (ll x)
{
	if (nums.empty()) return void (nums.pb(x));
	nums.pb(0);
	ll i;
	for (i=nums.sz()-1; i>=1 and nums[i-1] > x; i--)
		nums[i]=nums[i-1];
	nums[i]=x;
	// print (nums, n, "nums");
}

inline void del (ll x)
{
	ll i;
	for (i=0; nums[i]!=x; i++) ;
	f0r(i,i+1,nums.sz()-1) nums[i-1]=nums[i];
	nums.ppb();
}

inline ll calc()
{
	ll c=0, last=-INF;
	for (ll x:nums)
	{
		if (x-last > L)
		{
			last=x;
			c++;
		}
	}
	return c;
}

void init (int N, int l, int *X)
{
	n=N; L=l;
	ll i;
	f0r(i,0,n-1) ins(ar[i+1] = X[i]);
}

int update (int i, int x)
{
	i++;
	del(ar[i]);
	ins(ar[i]=x);
	return calc();
}

Compilation message

elephants.cpp: In function 'void del(ll)':
elephants.cpp:19:37: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define f0r(i,a,n) for ((i)=(a); (i)<=(n); (i)++)
      |                                  ~~~^~~~~
elephants.cpp:76:2: note: in expansion of macro 'f0r'
   76 |  f0r(i,i+1,nums.sz()-1) nums[i-1]=nums[i];
      |  ^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7768 KB Output is correct
2 Correct 1 ms 7768 KB Output is correct
3 Correct 1 ms 7772 KB Output is correct
4 Correct 1 ms 7772 KB Output is correct
5 Correct 1 ms 7772 KB Output is correct
6 Correct 1 ms 7772 KB Output is correct
7 Correct 1081 ms 8836 KB Output is correct
8 Correct 2271 ms 11100 KB Output is correct
9 Correct 3246 ms 9960 KB Output is correct
10 Correct 2433 ms 9944 KB Output is correct
11 Correct 2679 ms 9684 KB Output is correct
12 Correct 6126 ms 9932 KB Output is correct
13 Correct 2761 ms 9708 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7768 KB Output is correct
2 Correct 1 ms 7768 KB Output is correct
3 Correct 1 ms 7772 KB Output is correct
4 Correct 1 ms 7772 KB Output is correct
5 Correct 1 ms 7772 KB Output is correct
6 Correct 1 ms 7772 KB Output is correct
7 Correct 1081 ms 8836 KB Output is correct
8 Correct 2271 ms 11100 KB Output is correct
9 Correct 3246 ms 9960 KB Output is correct
10 Correct 2433 ms 9944 KB Output is correct
11 Correct 2679 ms 9684 KB Output is correct
12 Correct 6126 ms 9932 KB Output is correct
13 Correct 2761 ms 9708 KB Output is correct
14 Correct 1594 ms 9816 KB Output is correct
15 Correct 5132 ms 9816 KB Output is correct
16 Execution timed out 9066 ms 12240 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 7768 KB Output is correct
2 Correct 1 ms 7768 KB Output is correct
3 Correct 1 ms 7772 KB Output is correct
4 Correct 1 ms 7772 KB Output is correct
5 Correct 1 ms 7772 KB Output is correct
6 Correct 1 ms 7772 KB Output is correct
7 Correct 1081 ms 8836 KB Output is correct
8 Correct 2271 ms 11100 KB Output is correct
9 Correct 3246 ms 9960 KB Output is correct
10 Correct 2433 ms 9944 KB Output is correct
11 Correct 2679 ms 9684 KB Output is correct
12 Correct 6126 ms 9932 KB Output is correct
13 Correct 2761 ms 9708 KB Output is correct
14 Correct 1594 ms 9816 KB Output is correct
15 Correct 5132 ms 9816 KB Output is correct
16 Execution timed out 9066 ms 12240 KB Time limit exceeded
17 Halted 0 ms 0 KB -