oj.uz

Submission #348491

# Submission time Handle Problem Language Result Execution time Memory
348491 2021-01-15T05:17:55 Z arnold518 Queue (CEOI06_queue) C++14
0 / 100
 1000 ms 65540 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 = 5e4;
const int INF = 1e9+100;

int N, Q;
map<int, int> A, B, C;

int getA(int x)
{
	if(A.find(x)==A.end()) return x-1;
	return A[x];
}

int getB(int x)
{
	if(B.find(x)==B.end()) return x+1;
	return B[x];
}

int main()
{
	scanf("%d", &N);
	for(int i=1; i<=N; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		int p=getA(a), q=getB(a), r=getA(b); swap(b, r);
		B[p]=q;
		A[q]=p;
		A[a]=b;
		B[a]=r;
		B[b]=a;
		A[r]=a;
	}

	vector<pii> V;
	vector<int> V2;

	V.push_back({-1, -1});
	V2.push_back(0);

	int now=0;
	while(1)
	{
		if(B.find(now)!=B.end())
		{
			C[now]=V.size();
			V.push_back({now, now});
			V2.push_back(V2.back()+1);
			now=B[now];
		}
		else
		{
			auto it=B.lower_bound(now);
			if(it==B.end())
			{
				C[INF]=V.size();
				V.push_back({now, INF});
				V2.push_back(V2.back()+INF-now+1);
				break;
			}
			else
			{
				C[it->first-1]=V.size();
				V.push_back({now, it->first-1});
				V2.push_back(V2.back()+it->first-now);
				now=it->first;
			}
		}
	}

	for(int i=0; i<V.size(); i++)
	{
		printf("%d %d : %d\n", V[i].first, V[i].second, V2[i]);
	}

	scanf("%d", &Q);
	for(int i=1; i<=Q; i++)
	{
		char c; int x;
		scanf(" %c%d", &c, &x);

		if(c=='P')
		{
			int it=C.lower_bound(x)->second;
			int ans=V2[it-1]+x-V[it].first;
			printf("%d\n", ans);
		}
		else
		{
			x++;
			int it=lower_bound(V2.begin(), V2.end(), x)-V2.begin();
			int ans=V[it].first+x-V2[i-1]-1;
			printf("%d\n", ans);
		}
	}
}

Compilation message

queue.cpp: In function 'int main()':
queue.cpp:78:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for(int i=0; i<V.size(); i++)
      |               ~^~~~~~~~~
queue.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
queue.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   32 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~
queue.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   83 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
queue.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   87 |   scanf(" %c%d", &c, &x);
      |   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Expected integer, but ":" found
2 Runtime error 170 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 210 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Incorrect 4 ms 620 KB Expected integer, but ":" found
5 Incorrect 28 ms 2156 KB Expected integer, but ":" found
6 Incorrect 42 ms 3564 KB Expected integer, but ":" found
7 Incorrect 55 ms 4712 KB Expected integer, but ":" found
8 Incorrect 78 ms 7780 KB Expected integer, but ":" found
9 Incorrect 94 ms 8420 KB Expected integer, but ":" found
10 Incorrect 99 ms 9064 KB Expected integer, but ":" found
11 Incorrect 272 ms 19168 KB Expected integer, but ":" found
12 Incorrect 234 ms 12912 KB Expected integer, but ":" found
13 Incorrect 275 ms 19168 KB Expected integer, but ":" found
14 Incorrect 311 ms 19296 KB Expected integer, but ":" found
15 Incorrect 271 ms 19168 KB Expected integer, but ":" found
16 Incorrect 282 ms 19168 KB Expected integer, but ":" found
17 Runtime error 250 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 854 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 959 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Execution timed out 1044 ms 53924 KB Time limit exceeded
21 Incorrect 225 ms 18804 KB Expected integer, but ":" found
22 Incorrect 286 ms 21856 KB Expected integer, but ":" found
23 Incorrect 388 ms 26972 KB Expected integer, but ":" found
24 Incorrect 391 ms 26980 KB Expected integer, but ":" found
25 Incorrect 327 ms 18912 KB Expected integer, but ":" found