Submission #72211

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
72211	2018-08-26T06:02:01 Z	마릴린 희정(#2180, gs14004, ho94949)	Easy Data Structure Problem (FXCUP3_easy)	C++17	0 / 100	9 ms	6672 KB

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)
{
  for(auto& y: interv)
  {
    while(L[y] <= L[na] && R[na] <= R[y])
    {
      if(arr[y] == arr[2*y]) y = 2*y;
      else y = 2*y+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> 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)
    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;
}
/*
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()]);
}
*/

Compilation message

easy.cpp: In function 'int main()':
easy.cpp:52: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:57: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:68: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:70: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

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	6640 KB	Correct
2	Correct	7 ms	6640 KB	Correct
3	Incorrect	9 ms	6672 KB	Wrong
4	Halted	0 ms	0 KB	-

Subtask #2

0 / 67.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	6640 KB	Correct
2	Correct	7 ms	6640 KB	Correct
3	Incorrect	9 ms	6672 KB	Wrong
4	Halted	0 ms	0 KB	-