Submission #72390

#	Time	Username	Problem	Language	Result	Execution time	Memory
72390		이시대의진정한망겜스타투 (#118)	Easy Data Structure Problem (FXCUP3_easy)	C++17	0 / 100	5 ms	2864 KiB

easy

#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 && val[nxt] == X[i + 1]) {
		int temp = travel_to_right(X, i + 1, nxt);
		if(temp != -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 && val[nxt] == X[i - 1]) {
		int temp = travel_to_left(X, i - 1, nxt);
		if(temp != -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 (stderr)

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: 0 / 33
• Subtask 2: 0 / 67