oj.uz

Submission #72689

# Submission time Handle Problem Language Result Execution time Memory
72689 2018-08-26T15:17:18 Z gs14004 Easy Data Structure Problem (FXCUP3_easy) C++17
100 / 100
 161 ms 10572 KB 
#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> 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

easy.cpp: In function 'int main()':
easy.cpp:75: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:82: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:93: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:95: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.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7152 KB Correct
2 Correct 9 ms 7264 KB Correct
3 Correct 9 ms 7264 KB Correct
4 Correct 21 ms 7264 KB Correct
5 Correct 11 ms 7264 KB Correct
6 Correct 33 ms 7440 KB Correct
7 Correct 30 ms 7440 KB Correct
8 Correct 32 ms 7520 KB Correct

Subtask #2
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7152 KB Correct
2 Correct 9 ms 7264 KB Correct
3 Correct 9 ms 7264 KB Correct
4 Correct 21 ms 7264 KB Correct
5 Correct 11 ms 7264 KB Correct
6 Correct 33 ms 7440 KB Correct
7 Correct 30 ms 7440 KB Correct
8 Correct 32 ms 7520 KB Correct
9 Correct 52 ms 10376 KB Correct
10 Correct 52 ms 10376 KB Correct
11 Correct 50 ms 10376 KB Correct
12 Correct 108 ms 10376 KB Correct
13 Correct 108 ms 10376 KB Correct
14 Correct 150 ms 10488 KB Correct
15 Correct 161 ms 10488 KB Correct
16 Correct 133 ms 10488 KB Correct
17 Correct 124 ms 10572 KB Correct