oj.uz

Submission #72413

# Submission time Handle Problem Language Result Execution time Memory
72413 2018-08-26T07:52:39 Z 이시대의진정한망겜스타투(#2267, cki86201, ainta) Easy Data Structure Problem (FXCUP3_easy) C++17
100 / 100
 149 ms 10308 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ldouble;

int N, Q;
int A[100010];
int L;
int val[1<<18];
int lv[1<<18], rv[1<<18];
vector <int> idxs[100010];
int wc[100010];

int is_last(int x) {
	++x; if((x&-x) == x) return 1;
	return 0;
}
int is_first(int x) {
	if((x&-x) == x) return 1;
	return 0;
}

int travel_to_right(vector <int> &X, int i, int rt) {
	if(i == szz(X) - 1) return rv[rt] > N ? -1 : rv[rt];
	if(is_last(rt)) return -1;
	int nxt = 2 * rt + 2;
	while(nxt < 2 * L) {
		int temp;
		if(val[nxt] == X[i + 1] && (temp = travel_to_right(X, i + 1, nxt)) != -1) return temp;
		nxt *= 2;
	}
	return -1;
}

int travel_to_left(vector <int> &X, int i, int rt) {
	if(i == 0) return lv[rt];
	if(is_first(rt)) return -1;
	int nxt = 2 * rt - 1;
	while(nxt < 2 * L) {
		int temp;
		if(val[nxt] == X[i - 1] && (temp = travel_to_left(X, i - 1, nxt)) != -1) return temp;
		nxt = nxt * 2 + 1;
	}
	return -1;
}

pii chk(vector <int> &X, int i, int rt) {
	if(i > 0 && !is_first(rt) && rt % 2 == 0 && val[rt - 1] == X[i - 1]) {
		int rv = travel_to_right(X, i, rt);
		int lv = travel_to_left(X, i - 1, rt - 1);
		if(rv != -1 && lv != -1) return pii(lv, rv);
	}
	int rv = travel_to_right(X, i, rt);
	if(rv == -1) return pii(-1, -1);
	int lv = travel_to_left(X, i, rt);
	if(lv == -1) return pii(-1, -1);
	return pii(lv, rv);
}

void query(vector <int> X) {
	sort(all(X), [&](int x, int y) { return wc[x] < wc[y]; });
	rep(i, szz(X)) {
		int me = X[i];
		for(int rt : idxs[me]) {
			pii t = chk(X, i, rt);
			if(t.Fi != -1) {
				printf("%d %d\n", t.Fi, t.Se);
				return;
			}
		}
	}
	puts("-1");
}

int main() {
	scanf("%d%d", &N, &Q);
	for(int i=1;i<=N;i++) scanf("%d", A + i);
	for(int i=1;i<=N;i++) wc[A[i]] = i;
	L = 1;
	while(L < N) L *= 2;
	for(int i=1;i<=N;i++) {
		val[i + L - 1] = A[i];
	}
	for(int i=N+1;i<=L;i++) val[i+L-1] = 1e9;
	for(int i=L-1;i;i--) val[i] = min(val[i*2], val[i*2+1]);
	for(int i=L;i<2*L;i++) lv[i] = rv[i] = i - L + 1;
	for(int i=L-1;i;i--) lv[i] = lv[i*2], rv[i] = rv[i*2+1];
	for(int i=1;i<2*L;i++) if(rv[i] <= N) idxs[val[i]].pb(i);
	for(int i=1;i<=Q;i++) {
		int c; scanf("%d", &c);
		vector <int> v;
		rep(j, c) {
			int x; scanf("%d", &x);
			v.pb(x);
		}
		query(v);
	}
	return 0;
}

Compilation message

easy.cpp: In function 'int main()':
easy.cpp:102:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &Q);
  ~~~~~^~~~~~~~~~~~~~~~
easy.cpp:103:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=N;i++) scanf("%d", A + i);
                        ~~~~~^~~~~~~~~~~~~
easy.cpp:116:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int c; scanf("%d", &c);
          ~~~~~^~~~~~~~~~
easy.cpp:119:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int x; scanf("%d", &x);
           ~~~~~^~~~~~~~~~

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB Correct
2 Correct 5 ms 2680 KB Correct
3 Correct 4 ms 2824 KB Correct
4 Correct 14 ms 2824 KB Correct
5 Correct 6 ms 2900 KB Correct
6 Correct 23 ms 3120 KB Correct
7 Correct 17 ms 3120 KB Correct
8 Correct 21 ms 3120 KB Correct

Subtask #2
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB Correct
2 Correct 5 ms 2680 KB Correct
3 Correct 4 ms 2824 KB Correct
4 Correct 14 ms 2824 KB Correct
5 Correct 6 ms 2900 KB Correct
6 Correct 23 ms 3120 KB Correct
7 Correct 17 ms 3120 KB Correct
8 Correct 21 ms 3120 KB Correct
9 Correct 78 ms 10200 KB Correct
10 Correct 39 ms 10200 KB Correct
11 Correct 47 ms 10200 KB Correct
12 Correct 99 ms 10200 KB Correct
13 Correct 110 ms 10200 KB Correct
14 Correct 149 ms 10284 KB Correct
15 Correct 132 ms 10284 KB Correct
16 Correct 135 ms 10284 KB Correct
17 Correct 121 ms 10308 KB Correct