oj.uz

Submission #363549

# Submission time Handle Problem Language Result Execution time Memory
363549 2021-02-06T14:23:54 Z arnold518 OGLEDALA (COI15_ogledala) C++14
41 / 100
 4000 ms 266788 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 3e5;

ll M;
int N, Q;
ll A[MAXN+10], B[MAXN+10];

struct Data
{
	ll l, r;
	bool operator < (const Data &p) const
	{
		if(r-l!=p.r-p.l) return r-l<p.r-p.l;
		return l>p.l;
	}
};

priority_queue<Data> PQ;

int main()
{
	scanf("%lld%d%d", &M, &N, &Q);
	for(int i=1; i<=N; i++) scanf("%lld", &A[i]);
	for(int i=1; i<=Q; i++) scanf("%lld", &B[i]);

	ll bef=1;
	for(int i=1; i<=N; i++)
	{
		if(bef<A[i])
		{
			PQ.push({bef, A[i]-1});
		}
		bef=A[i]+1;
	}
	if(bef<M+1)
	{
		PQ.push({bef, M});
	}

	int j;
	for(j=1; j<=Q; j++)
	{
		if(B[j]<=N) printf("%lld\n", A[B[j]]);
		else break;
	}
	for(int i=1; j<=Q; i++)
	{
		Data p=PQ.top(); PQ.pop();
		ll mid=p.l+p.r>>1;
		if(p.l<=mid-1) PQ.push({p.l, mid-1});
		if(mid+1<=p.r) PQ.push({mid+1, p.r});
		if(B[j]-N==i)
		{
			printf("%lld\n", mid);
			j++;
		}
	}
}

Compilation message

ogledala.cpp: In function 'int main()':
ogledala.cpp:55:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |   ll mid=p.l+p.r>>1;
      |          ~~~^~~~
ogledala.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |  scanf("%lld%d%d", &M, &N, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
ogledala.cpp:29:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   29 |  for(int i=1; i<=N; i++) scanf("%lld", &A[i]);
      |                          ~~~~~^~~~~~~~~~~~~~~
ogledala.cpp:30:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   30 |  for(int i=1; i<=Q; i++) scanf("%lld", &B[i]);
      |                          ~~~~~^~~~~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 34 ms 2916 KB Output is correct
4 Correct 31 ms 2916 KB Output is correct
5 Correct 96 ms 5724 KB Output is correct
6 Correct 86 ms 5904 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 8792 KB Output is correct
2 Correct 53 ms 8864 KB Output is correct
3 Correct 138 ms 13268 KB Output is correct
4 Correct 96 ms 13396 KB Output is correct
5 Correct 105 ms 13652 KB Output is correct
6 Correct 113 ms 13652 KB Output is correct

Subtask #3
0 / 59.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4096 ms 266788 KB Time limit exceeded
2 Halted 0 ms 0 KB -