oj.uz

Submission #72258

# Submission time Handle Problem Language Result Execution time Memory
72258 2018-08-26T06:28:33 Z (#2175, xdoju, kazel, pps789) Easy Data Structure Problem (FXCUP3_easy) C++17
100 / 100
 68 ms 5164 KB 
#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;
}

Compilation message

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.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3320 KB Correct
2 Correct 5 ms 3428 KB Correct
3 Correct 5 ms 3556 KB Correct
4 Correct 16 ms 3556 KB Correct
5 Correct 6 ms 3556 KB Correct
6 Correct 25 ms 3604 KB Correct
7 Correct 21 ms 3604 KB Correct
8 Correct 23 ms 3604 KB Correct

Subtask #2
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3320 KB Correct
2 Correct 5 ms 3428 KB Correct
3 Correct 5 ms 3556 KB Correct
4 Correct 16 ms 3556 KB Correct
5 Correct 6 ms 3556 KB Correct
6 Correct 25 ms 3604 KB Correct
7 Correct 21 ms 3604 KB Correct
8 Correct 23 ms 3604 KB Correct
9 Correct 20 ms 4372 KB Correct
10 Correct 25 ms 4372 KB Correct
11 Correct 26 ms 4372 KB Correct
12 Correct 56 ms 4608 KB Correct
13 Correct 68 ms 4608 KB Correct
14 Correct 54 ms 4960 KB Correct
15 Correct 62 ms 4960 KB Correct
16 Correct 61 ms 5164 KB Correct
17 Correct 58 ms 5164 KB Correct