oj.uz

Submission #136358

# Submission time Handle Problem Language Result Execution time Memory
136358 2019-07-25T07:49:59 Z gs14004 Queue (CEOI06_queue) C++17
50 / 100
 327 ms 16460 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);
			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: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 376 KB Partially correct
2 Partially correct 2 ms 248 KB Partially correct
3 Partially correct 3 ms 376 KB Partially correct
4 Partially correct 2 ms 632 KB Partially correct
5 Partially correct 27 ms 1108 KB Partially correct
6 Partially correct 45 ms 2168 KB Partially correct
7 Partially correct 50 ms 2808 KB Partially correct
8 Partially correct 64 ms 4340 KB Partially correct
9 Partially correct 78 ms 4852 KB Partially correct
10 Partially correct 93 ms 5312 KB Partially correct
11 Partially correct 252 ms 11792 KB Partially correct
12 Partially correct 301 ms 9708 KB Partially correct
13 Partially correct 263 ms 11972 KB Partially correct
14 Partially correct 259 ms 11752 KB Partially correct
15 Partially correct 249 ms 11756 KB Partially correct
16 Partially correct 293 ms 11884 KB Partially correct
17 Partially correct 46 ms 376 KB Partially correct
18 Partially correct 53 ms 1120 KB Partially correct
19 Partially correct 91 ms 1528 KB Partially correct
20 Partially correct 142 ms 1976 KB Partially correct
21 Partially correct 181 ms 11364 KB Partially correct
22 Partially correct 247 ms 13464 KB Partially correct
23 Partially correct 327 ms 16364 KB Partially correct
24 Partially correct 325 ms 16460 KB Partially correct
25 Partially correct 285 ms 12920 KB Partially correct