제출 #72258

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
72258		(#118)	흔한 자료구조 문제 (FXCUP3_easy)	C++17	100 / 100	68 ms	5164 KiB

easy

#include <cstdio>
#include <algorithm>
#include <climits>
using namespace std;

int p[100002];
int rev[100002];

int need[100002];

int tr[1 << 18]; const int O = 1 << 17;
int rs[1 << 18], re[1 << 18];

int main(){
  int N, Q; scanf("%d%d", &N, &Q);

  for(int i = 1; i <= N; i++){
    int x; scanf("%d", &x);
    p[i] = x; rev[x] = i; tr[O + i - 1] = x;
  }

  for(int i = N + 1; i <= O; i++) tr[O + i - 1] = INT_MAX;

  for(int i = 1; i <= O; i++){
    rs[O + i - 1] = i; re[O + i - 1] = i;
  }

  for(int i = O - 1; i >= 1; i--){
    tr[i] = min(tr[i * 2], tr[i * 2 + 1]);
    rs[i] = rs[i * 2];
    re[i] = re[i * 2 + 1];
  }

  for(int q = 1; q <= Q; q++){
    int M; scanf("%d", &M);

    int minIndex = N + 1, maxIndex = 0;

    for(int i = 1; i <= M; i++){
      int x; scanf("%d", &x);

      need[x] = q;

      int r = rev[x];

      if(r < minIndex) minIndex = r;
      if(r > maxIndex) maxIndex = r;
    }

    bool found = false;

    int vs = p[minIndex], ve = p[maxIndex];

    for(int i = minIndex + O - 1; !found && i > 0; i /= 2){
      if(tr[i] != vs) break;

      for(int j = maxIndex + O - 1; !found && j > 0; j /= 2){
        if(tr[j] != ve) break;

        int ss = rs[i], ee = re[j]; // 실제 쿼리
        if(ss < 1 || ee > N) continue;

        // printf("try %d %d\n", ss, ee);

        int xx = O + ss - 1, yy = O + ee - 1;
        int rem = M; bool valid = true;

        while(xx <= yy){
          if(xx & 1){
            // tr[x] 참조

            // printf("visit %d\n", tr[xx]);
            if(need[tr[xx]] != q){ valid = false; break; }
            rem--; xx++;
          }
          if(~yy & 1){
            // printf("visit %d\n", tr[yy]);
            if(need[tr[yy]] != q){ valid = false; break; }
            rem--; yy--;
          }

          xx /= 2; yy /= 2;
        }

        if(valid && rem == 0){ printf("%d %d\n", ss, ee); found = true; }
      }
    }

    if(!found) puts("-1");
  }

  for(; Q--; ){
    int M; scanf("%d", &M);
  }
  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

easy.cpp: In function 'int main()':
easy.cpp:15:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int N, Q; scanf("%d%d", &N, &Q);
             ~~~~~^~~~~~~~~~~~~~~~
easy.cpp:18:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int x; scanf("%d", &x);
            ~~~~~^~~~~~~~~~
easy.cpp:35:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int M; scanf("%d", &M);
            ~~~~~^~~~~~~~~~
easy.cpp:40:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       int x; scanf("%d", &x);
              ~~~~~^~~~~~~~~~
easy.cpp:93:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int M; scanf("%d", &M);
            ~~~~~^~~~~~~~~~

• Subtask 1: 33 / 33
• Subtask 2: 67 / 67