oj.uz

Submission #136273

# Submission time Handle Problem Language Result Execution time Memory
136273 2019-07-25T05:21:56 Z 김현수(#3358) Queue (CEOI06_queue) C++14
76 / 100
 451 ms 20324 KB 
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;

typedef pair<int,int> pii;
const int N = 50005, inf = 1e9+7;

map<int, int> fr, bk;
set<pii> s[2];

int getfr (int I) {
	if(fr.find(I) == fr.end()) return I-1;
	return fr[I];
}

int getbk (int I) {
	if(bk.find(I) == bk.end()) return I+1;
	return bk[I];
}

int main()
{
	int n, q;
	scanf("%d",&n);
	bk[inf] = inf;
	int CT = 1;
	while(n--) {
		int A, B;
		scanf("%d%d",&A,&B);
		int AF = getfr(A), AB = getbk(A), BF = getfr(B);
		if(A == B || AB == B) continue;
		fr[AB] = AF;
		bk[AF] = AB;
		fr[A] = BF;
		bk[BF] = A;
		fr[B] = A;
		bk[A] = B;
		if(CT == B) CT = A;
	}
	for(int i=CT,j=1;i<inf;) {
		auto it = bk.lower_bound(i);
		int E = (*it).X;
		j += E-i;
		s[0].insert({E, j});
		s[1].insert({j, E});
		i = (*it).Y;
		j++;
	}
	scanf("%d",&q);
	while(q--) {
		char T[2]; int A;
		scanf("%s%d",T,&A);
		auto it = s[T[0]=='L'].lower_bound({A, 0});
		printf("%d\n", (*it).Y - (*it).X + A);
	}
}

Compilation message

queue.cpp: In function 'int main()':
queue.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
queue.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&A,&B);
   ~~~~~^~~~~~~~~~~~~~
queue.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
queue.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s%d",T,&A);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
76.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 33 ms 1372 KB Output is correct
6 Correct 44 ms 2424 KB Output is correct
7 Correct 65 ms 3440 KB Output is correct
8 Correct 93 ms 5628 KB Output is correct
9 Correct 101 ms 6028 KB Output is correct
10 Correct 110 ms 6520 KB Output is correct
11 Correct 298 ms 14444 KB Output is correct
12 Correct 267 ms 11892 KB Output is correct
13 Correct 318 ms 14436 KB Output is correct
14 Incorrect 238 ms 9552 KB Output isn't correct
15 Incorrect 255 ms 10568 KB Output isn't correct
16 Correct 318 ms 14460 KB Output is correct
17 Correct 30 ms 504 KB Output is correct
18 Incorrect 53 ms 1064 KB Output isn't correct
19 Correct 91 ms 1956 KB Output is correct
20 Incorrect 140 ms 1948 KB Output isn't correct
21 Incorrect 207 ms 12316 KB Output isn't correct
22 Correct 315 ms 16548 KB Output is correct
23 Correct 451 ms 20324 KB Output is correct
24 Incorrect 343 ms 16608 KB Output isn't correct
25 Correct 359 ms 15856 KB Output is correct