Submission #72398

#	Time	Username	Problem	Language	Result	Execution time	Memory
72398		마릴린 희정 (#118)	Easy Data Structure Problem (FXCUP3_easy)	C++17	100 / 100	160 ms	10656 KiB

easy

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 131072;
int N, Q;
int arr[2*MAXN];
int L[2*MAXN];
int R[2*MAXN];
vector<int> idx[MAXN];
void add(vector<int>& interv, int na)
{
	while(R[na] >= N){
		if(arr[na] == arr[2*na]) na = 2*na;
		else na = 2*na+1;
	}

	for(auto& y: interv)
	{
		while(L[na] <= L[y] && R[y] <= R[na])
		{
			if(arr[na] == arr[2*na]) na = 2*na;
			else na = 2*na+1;
		}
	}
	interv.push_back(na);
}

vector<int> query(int s, int e){
	if(s > e){
		vector<int> ans = {-1};
		return ans;
	}
	s += MAXN; e += MAXN;
	vector<int> ans;
	while(s <= e){
		if(s%2 == 1) ans.push_back(arr[s++]);
		if(e%2 == 0) ans.push_back(arr[e--]);
		s >>= 1;
		e >>= 1;
	}
	sort(ans.begin(), ans.end());
	return ans;
}

pair<int, int> verify(vector<int> interv, vector<int> actual)
{
	sort(actual.begin(), actual.end());
	sort(interv.begin(), interv.end(), [&](const int &a, const int &b){
		return L[a] < L[b];
	});
	vector<int> ans;
	int s = MAXN, e = 0;
	for(auto x: interv) s = min(s, L[x]), e = max(e, R[x]);
	if(query(s, e) == actual) return make_pair(s, e);
	if(interv.size() >= 2){
		int ns = (interv[0] < MAXN ? L[2 * interv[0] + 1] : 0);
		int ne = (interv.back() < MAXN ? R[2 * interv.back()] : 0);
		if(ns != 0 && query(ns, e) == actual) return make_pair(ns, e);
		if(ne != 0 && query(s, ne) == actual) return make_pair(s, ne);
		if(ns && ne && query(ns, ne) == actual) return make_pair(ns, ne);
	}
	return make_pair(-1, -1);
}
/*
pair<int, int> verify(vector<int> interv)
{
  
  sort(interv.begin(), interv.end(), 
    [](int a, int b){ return L[a] < L[b]; });
  for(int i=0; i<(int)interv.size()-1; ++i)
  {
    int lv = interv[i], rv = interv[i+1];
    if(R[lv]+1 != L[rv]) return make_pair(-1, -1);
    if(lv+1 == rv && lv%2==0) return make_pair(-1, -1);
  }
  return make_pair(L[interv[0]], R[interv.back()]);
}
*/
pair<int, int> solve(vector<int> query)
{
  vector<int> queryfarm;
  sort(query.begin(), query.end(), [](int x, int y){
    return idx[x].back() > idx[y].back(); });
  for(auto x: query)
    add(queryfarm, idx[x].back());
  return verify(queryfarm, query);
}
int main()
{
  scanf("%d%d", &N, &Q);
  for(int i=0; i<MAXN; ++i){
  	  arr[i + MAXN] = N + 10;
    L[i+MAXN] = R[i+MAXN] = i;
  }
  for(int i=0; i<N; ++i)
  {
    scanf("%d", arr+i+MAXN);
    idx[arr[i+MAXN]].push_back(i+MAXN);
  }
  for(int i=MAXN-1; i>=1; --i)
  {
    L[i] = L[2*i]; R[i] = R[2*i+1];
    arr[i] = min(arr[2*i], arr[2*i+1]);
    idx[arr[i]].push_back(i);
  }
  for(int j=0; j<Q; ++j)
  {
    int T; scanf("%d", &T);
    vector<int> a(T);
    for(int i=0; i<T; ++i) scanf("%d", &a[i]);
    pair<int, int> res = solve(a);
    if(res.first == -1) puts("-1");
    else printf("%d %d\n", res.first+1, res.second+1);
  }
  return 0;
}

Compilation message (stderr)

easy.cpp: In function 'int main()':
easy.cpp:89:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &N, &Q);
   ~~~~~^~~~~~~~~~~~~~~~
easy.cpp:96:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", arr+i+MAXN);
     ~~~~~^~~~~~~~~~~~~~~~~~
easy.cpp:107:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int T; scanf("%d", &T);
            ~~~~~^~~~~~~~~~
easy.cpp:109:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=0; i<T; ++i) scanf("%d", &a[i]);
                            ~~~~~^~~~~~~~~~~~~

• Subtask 1: 33 / 33
• Subtask 2: 67 / 67