oj.uz

답안 #72366

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
72366 2018-08-26T07:30:47 Z 마릴린 희정(#2180, gs14004, ho94949) 흔한 자료구조 문제 (FXCUP3_easy) C++17
0 / 100
 10 ms 7268 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);
}
pair<int, int> verify(vector<int> interv)
{
  vector<int> ans;
  int s = MAXN, e = 0;
  for(auto x: interv) s = min(s, L[x]), e = max(e, R[x]);
  int rs = s, re = e;
  s += MAXN; e += MAXN;
  while (s <= e)
  {
    if(s%2 == 1)
      ans.push_back(s++);
    if(e%2 == 0)
      ans.push_back(e--);
    s /= 2; e /= 2;
  }
  sort(ans.begin(), ans.end());
  sort(interv.begin(), interv.end());
  if(ans == interv) return make_pair(rs, re);
  else 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);
}
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:72: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:79: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:90: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:92: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
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7152 KB Correct
2 Correct 10 ms 7168 KB Correct
3 Incorrect 8 ms 7268 KB Wrong
4 Halted 0 ms 0 KB -

Subtask #2
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7152 KB Correct
2 Correct 10 ms 7168 KB Correct
3 Incorrect 8 ms 7268 KB Wrong
4 Halted 0 ms 0 KB -