oj.uz

Submission #136359

# Submission time Handle Problem Language Result Execution time Memory
136359 2019-07-25T07:50:20 Z gs14004 Queue (CEOI06_queue) C++17
50 / 100
 372 ms 16236 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int inf = 1e9;
 
map<int, int> nxt, prv, low;
 
int getprv(int x){
	if(prv.find(x) != prv.end()) return prv[x];
	return x - 1;
}
 
int getnxt(int x){
	if(nxt.find(x) != nxt.end()) return nxt[x];
	return x + 1;
}
 
int main(){
	int n;
	scanf("%d",&n);
	for(int i=0; i<n; i++){
		int a, b;
		scanf("%d %d",&a,&b);
		int pa = getprv(a);
		int na = getnxt(a);
		nxt[pa] = na;
		prv[na] = pa;
		int pb = getprv(b);
		nxt[pb] = a;
		prv[a] = pb;
		nxt[a] = b;
		prv[b] = a;
	}
	vector<pi> interval;
	vector<int> length;
	int p = 0;
	while(1){
		auto t = nxt.lower_bound(p);
		if(t == nxt.end()){
			interval.emplace_back(p, inf);
			break;
		}
		interval.emplace_back(p, t->first);
		p = t->second;
	}
	int cnt = 0;
	for(auto &i : interval){
		low[i.first] = cnt;
		cnt += i.second - i.first + 1;
		length.push_back(cnt);
	}
	int q;
	scanf("%d",&q);
	while(q--){
		char buf[5];
		int x;
		scanf("%s %d",buf,&x);
		if(*buf == 'L'){
			x++;
			int p = lower_bound(length.begin(), length.end(), x) - length.begin();
			if(p) x -= length[p-1];
			printf("%d\n",interval[p].first + x - 1);
        //  puts("69");
		}
		else{
			int cnt = 0;
			auto p = --low.upper_bound(x);
          puts("69");
		//	printf("%d\n", p->second + x - p->first);
		}
	}
}

Compilation message

queue.cpp: In function 'int main()':
queue.cpp:84:8: warning: unused variable 'cnt' [-Wunused-variable]
    int cnt = 0;
        ^~~
queue.cpp:85:9: warning: variable 'p' set but not used [-Wunused-but-set-variable]
    auto p = --low.upper_bound(x);
         ^
queue.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
queue.cpp:41: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:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
queue.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s %d",buf,&x);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
50.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 256 KB Partially correct
2 Partially correct 2 ms 376 KB Partially correct
3 Partially correct 3 ms 376 KB Partially correct
4 Partially correct 5 ms 504 KB Partially correct
5 Partially correct 27 ms 1140 KB Partially correct
6 Partially correct 39 ms 1784 KB Partially correct
7 Partially correct 53 ms 2820 KB Partially correct
8 Partially correct 72 ms 4724 KB Partially correct
9 Partially correct 78 ms 4904 KB Partially correct
10 Partially correct 84 ms 5368 KB Partially correct
11 Partially correct 250 ms 11784 KB Partially correct
12 Partially correct 212 ms 9788 KB Partially correct
13 Partially correct 243 ms 11896 KB Partially correct
14 Partially correct 257 ms 11960 KB Partially correct
15 Partially correct 235 ms 12012 KB Partially correct
16 Partially correct 249 ms 11756 KB Partially correct
17 Partially correct 28 ms 536 KB Partially correct
18 Partially correct 53 ms 1272 KB Partially correct
19 Partially correct 82 ms 1528 KB Partially correct
20 Partially correct 144 ms 2344 KB Partially correct
21 Partially correct 214 ms 11392 KB Partially correct
22 Partially correct 310 ms 13564 KB Partially correct
23 Partially correct 328 ms 16236 KB Partially correct
24 Partially correct 372 ms 16236 KB Partially correct
25 Partially correct 295 ms 12880 KB Partially correct