oj.uz

Submission #123634

# Submission time Handle Problem Language Result Execution time Memory
123634 2019-07-01T20:23:46 Z MetB OGLEDALA (COI15_ogledala) C++14
100 / 100
 2824 ms 334996 KB 
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <string.h>
#include <cstdlib>
#include <vector>
#include <string>
#include <bitset>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
 
typedef long long ll;
typedef long double ld;
 
const ll MOD = 1e9 + 7, INF = 1e18 + 1;
 
using namespace std;

unordered_map <ll, ll> d;

ll a[100000], n, m, q;

struct seg
{
	ll x, c, i;

	bool operator < (const seg& b) const
	{
		return (x == b.x ? i < b.i : x > b.x);
	}
};

vector <seg> v;

vector < pair <ll, ll> > descend (ll x)
{
	vector < pair <ll, ll> > v;

	v.push_back ({x, 1});

	ll mult_l = 1, mult_r = 1, l = (x - 1) / 2, r = x - 1 - l, n_l, n_r;

	while (l > 0 || r > 0)
	{
		if (l == r) 
		{
			v.push_back ({l, mult_l + mult_r});
			n_l = (l - 1) / 2;
			n_r = l - 1 - n_l;
			mult_l = mult_r = mult_l + mult_r;
		}
		else
		{
			if (l > 0) v.push_back ({l, mult_l});
			if (r > 0) v.push_back ({r, mult_r});
			n_l = (l - 1) / 2;
			n_r = (r - 1) / 2;

			if (2 * n_l == l - 1) 
			{
				mult_l = 2 * mult_l + mult_r;
				if (n_r == n_l) n_r = r - 1 - n_r;
			}
			else 
			{
				mult_r = mult_l + 2 * mult_r;
				if (n_r == n_l) n_l = l - 1 - n_l;
			}
		}

		l = n_l;
		r = n_r;
	}

	return v;
}

void calc (ll x, ll key)
{
	if (d.find (x) != d.end ()) return;

	if (x == key) 
	{
		d[x] = 1;
		return;
	}

	if (x < 1) 
	{
		d[x] = 0;
		return;
	}

	ll n_l = (x - 1) / 2, n_r = x - 1 - n_l;

	calc (n_l, key);
	calc (n_r, key);

	d[x] = d[n_l] + d[n_r];
}


ll ord_stat (ll x, ll c, ll len, ll l, ll r)
{
	if (len == x) return (l + r) / 2;
	ll m = (l + r) / 2;
	ll len_l = (len - 1) / 2, len_r = len - 1 - len_l;
 
	ll v_l = d[len_l], v_r = d[len_r];

	if (v_l >= c) return ord_stat (x, c, len_l, l, m - 1);
	else return ord_stat (x, c - v_l, len_r, m + 1, r);
}

int main ()
{
	cin >> m >> n >> q;

	for (ll i = 0; i < n; i++)
	{
		scanf ("%lld", &a[i]);

		auto s = descend (a[i] - (i ? a[i-1] : 0) - 1);

		for (auto k : s)
			v.push_back ({k.first, k.second, i});
	}

	auto s = descend (m - (n ? a[n-1] : 0));

	vector <seg> b;

	for (auto k : s)
		v.push_back ({k.first, k.second, n});

	sort (v.begin (), v.end ());

	for (auto a : v)
	{
		if (b.empty () || b.back ().x != a.x || b.back ().i != a.i)
			b.push_back (a);
		else b[b.size () - 1].c += a.c;
	}

	v = b;

	ll ptr = 0, sum = 0;

	for (int i = 0; i < q; i++)
	{
		ll b;
		scanf ("%lld", &b);

		if (b <= n)
		{
			printf ("%lld\n", a[b-1]);
			continue;
		}
		b -= n;
		if (sum + v[ptr].c < b)
		{
			do
			{
				sum += v[ptr].c;
				ptr++;
			}
			while (ptr != v.size () && sum + v[ptr].c < b);
		}
 
		ll l = (v[ptr].i ? a[v[ptr].i - 1] + 1 : 1), r = (v[ptr].i != n ? a[v[ptr].i] - 1 : m);
		d.clear ();
 
		calc (r - l + 1, v[ptr].x);
 
		printf ("%lld\n", ord_stat (v[ptr].x, b - sum, r - l + 1, l, r));
	}
}

Compilation message

ogledala.cpp: In function 'll ord_stat(ll, ll, ll, ll, ll)':
ogledala.cpp:112:21: warning: unused variable 'v_r' [-Wunused-variable]
  ll v_l = d[len_l], v_r = d[len_r];
                     ^~~
ogledala.cpp: In function 'int main()':
ogledala.cpp:170:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while (ptr != v.size () && sum + v[ptr].c < b);
           ~~~~^~~~~~~~~~~~
ogledala.cpp:124:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%lld", &a[i]);
   ~~~~~~^~~~~~~~~~~~~~~
ogledala.cpp:155:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%lld", &b);
   ~~~~~~^~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 94 ms 3948 KB Output is correct
4 Correct 80 ms 4072 KB Output is correct
5 Correct 117 ms 15576 KB Output is correct
6 Correct 109 ms 15704 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 764 KB Output is correct
2 Correct 37 ms 824 KB Output is correct
3 Correct 1713 ms 316092 KB Output is correct
4 Correct 1606 ms 319228 KB Output is correct
5 Correct 1876 ms 331724 KB Output is correct
6 Correct 1810 ms 334820 KB Output is correct

Subtask #3
59.0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 1406 ms 169304 KB Output is correct
2 Correct 1450 ms 173620 KB Output is correct
3 Correct 2122 ms 300456 KB Output is correct
4 Correct 2156 ms 303504 KB Output is correct
5 Correct 2660 ms 331716 KB Output is correct
6 Correct 2824 ms 334996 KB Output is correct