oj.uz

Submission #72177

# Submission time Handle Problem Language Result Execution time Memory
72177 2018-08-26T05:47:18 Z 마릴린 희정(#2180, gs14004, ho94949) Easy Data Structure Problem (FXCUP3_easy) C++17
0 / 100
 10 ms 6824 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[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)
{
  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)
    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:44: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:49: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:60: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:62: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 8 ms 6512 KB Correct
2 Correct 10 ms 6620 KB Correct
3 Incorrect 8 ms 6824 KB Wrong
4 Halted 0 ms 0 KB -

Subtask #2
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6512 KB Correct
2 Correct 10 ms 6620 KB Correct
3 Incorrect 8 ms 6824 KB Wrong
4 Halted 0 ms 0 KB -