oj.uz

Submission #72154

# Submission time Handle Problem Language Result Execution time Memory
72154 2018-08-26T05:36:16 Z 마릴린 희정(#2180, gs14004, ho94949) Easy Data Structure Problem (FXCUP3_easy) C++17
0 / 100
 12 ms 6748 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)
{
  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<pair<int, int> > total;
  for(auto x: interv)
    total.emplace_back(L[x], R[x]);
  sort(total.begin(), total.end());
  for(int i=0; i<(int)total.size()-1; ++i)
  {
    if(total[i].second+1!=total[i+1].first) return make_pair(-1, -1);
  }
  return make_pair(total[0].first, total.back().second);
}
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;
}

Compilation message

easy.cpp: In function 'int main()':
easy.cpp:42: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:47: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:58: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:60: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 12 ms 6640 KB Correct
2 Incorrect 12 ms 6748 KB Wrong
3 Halted 0 ms 0 KB -

Subtask #2
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 6640 KB Correct
2 Incorrect 12 ms 6748 KB Wrong
3 Halted 0 ms 0 KB -