oj.uz

답안 #123503

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
123503 2019-07-01T14:07:25 Z MetB OGLEDALA (COI15_ogledala) C++14
19 / 100
 2506 ms 524292 KB 
#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;

map <ll, vector < pair <ll, ll> > > d;

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

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

	ll l = (x - 1) / 2, r = x - 1 - l;

	calc (l);
	calc (r);

	ll ptr1 = 0, ptr2 = 0;

	auto& v = d[x], v_l = d[l], v_r = d[r];

	while (ptr1 != v_l.size () || ptr2 != v_r.size ())
	{
		if (ptr1 != v_l.size () && ptr2 != v_r.size () && v_l[ptr1].first == v_r[ptr2].first)
		{
			v.emplace_back (v_l[ptr1].first, v_l[ptr1].second + v_r[ptr2].second);

			ptr1++;
			ptr2++;

			continue;
		}

		if (ptr1 < v_l.size () && (ptr2 == v_r.size () || v_l[ptr1] < v_r[ptr2]))
		{
			v.push_back (v_l[ptr1]);
			ptr1++;
		}
		else
		{
			v.push_back (v_r[ptr2]);
			ptr2++;
		}
	}

	v.emplace_back (x, 1);
}

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 k = lower_bound (d[len_l].begin (), d[len_l].end (), make_pair (x, 0LL)) - d[len_l].begin ();

	if (k != d[len_l].size () && d[len_l][k].first == x)
	{
		if (d[len_l][k].second >= c) return ord_stat (x, c, len_l, l, m - 1);
		else return ord_stat (x, c - d[len_l][k].second, len_r, m + 1, r);
	}
	else return ord_stat (x, c, len_r, m + 1, r);
}

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;

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

	for (ll i = 0; i < n; i++)
	{
		scanf ("%lld", &a[i]);
		
		if (i) calc (a[i] - a[i-1] - 1);
		else calc (a[i] - 1);
	}

	calc (m - (n ? a[n-1] : 0));

	for (ll i = 0; i < n; i++)
		for (auto x : d[a[i] - (i ? a[i-1] : 0) - 1])
			v.push_back ({x.first, x.second, i});

	for (auto x : d[m - (n ? a[n-1] : 0)])
			v.push_back ({x.first, x.second, n});	

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

	ll sum = 0, ptr = 0;

	for (ll 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);

		printf ("%lld\n", ord_stat (v[ptr].x, b - sum, r - l + 1, l, r));
	}
}

Compilation message

ogledala.cpp: In function 'void calc(ll)':
ogledala.cpp:39:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (ptr1 != v_l.size () || ptr2 != v_r.size ())
         ~~~~~^~~~~~~~~~~~~~
ogledala.cpp:39:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (ptr1 != v_l.size () || ptr2 != v_r.size ())
                                ~~~~~^~~~~~~~~~~~~~
ogledala.cpp:41:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (ptr1 != v_l.size () && ptr2 != v_r.size () && v_l[ptr1].first == v_r[ptr2].first)
       ~~~~~^~~~~~~~~~~~~~
ogledala.cpp:41:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (ptr1 != v_l.size () && ptr2 != v_r.size () && v_l[ptr1].first == v_r[ptr2].first)
                              ~~~~~^~~~~~~~~~~~~~
ogledala.cpp:51:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (ptr1 < v_l.size () && (ptr2 == v_r.size () || v_l[ptr1] < v_r[ptr2]))
       ~~~~~^~~~~~~~~~~~~
ogledala.cpp:51:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (ptr1 < v_l.size () && (ptr2 == v_r.size () || v_l[ptr1] < v_r[ptr2]))
                              ~~~~~^~~~~~~~~~~~~~
ogledala.cpp: In function 'll ord_stat(ll, ll, ll, ll, ll)':
ogledala.cpp:74:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (k != d[len_l].size () && d[len_l][k].first == x)
      ~~^~~~~~~~~~~~~~~~~~~
ogledala.cpp: In function 'int main()':
ogledala.cpp:136:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while (ptr != v.size () && sum + v[ptr].c < b);
           ~~~~^~~~~~~~~~~~
ogledala.cpp:100:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%lld", &a[i]);
   ~~~~~~^~~~~~~~~~~~~~~
ogledala.cpp:122: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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 44 ms 2032 KB Output is correct
4 Correct 38 ms 2032 KB Output is correct
5 Correct 76 ms 7400 KB Output is correct
6 Correct 70 ms 7432 KB Output is correct

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 2744 KB Output is correct
2 Correct 22 ms 2872 KB Output is correct
3 Runtime error 2113 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 59.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2506 ms 194440 KB Output is correct
2 Correct 2447 ms 182708 KB Output is correct
3 Runtime error 2170 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -