oj.uz

Submission #72398

# Submission time Handle Problem Language Result Execution time Memory
72398 2018-08-26T07:44:44 Z 마릴린 희정(#2180, gs14004, ho94949) Easy Data Structure Problem (FXCUP3_easy) C++17
100 / 100
 160 ms 10656 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> 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

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.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7024 KB Correct
2 Correct 11 ms 7132 KB Correct
3 Correct 11 ms 7208 KB Correct
4 Correct 25 ms 7244 KB Correct
5 Correct 15 ms 7244 KB Correct
6 Correct 35 ms 7308 KB Correct
7 Correct 28 ms 7428 KB Correct
8 Correct 32 ms 7428 KB Correct

Subtask #2
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7024 KB Correct
2 Correct 11 ms 7132 KB Correct
3 Correct 11 ms 7208 KB Correct
4 Correct 25 ms 7244 KB Correct
5 Correct 15 ms 7244 KB Correct
6 Correct 35 ms 7308 KB Correct
7 Correct 28 ms 7428 KB Correct
8 Correct 32 ms 7428 KB Correct
9 Correct 46 ms 10352 KB Correct
10 Correct 57 ms 10352 KB Correct
11 Correct 48 ms 10352 KB Correct
12 Correct 99 ms 10352 KB Correct
13 Correct 104 ms 10352 KB Correct
14 Correct 133 ms 10508 KB Correct
15 Correct 131 ms 10508 KB Correct
16 Correct 152 ms 10656 KB Correct
17 Correct 160 ms 10656 KB Correct