Submission #897653

---

Source Code Expand

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

int main() {
  int N, M, Q; scanf("%d%d%d", &N, &M, &Q);
  static pair<int,int> queries[100000];
  for(int i = 0; i < Q; ++i) {
    scanf("%d", &queries[i].first); --queries[i].first;
    queries[i].second = i;
  }
  sort(queries, queries+Q);
  // printf("queries = ");
  // for(int i = 0; i < Q; ++i) {
  //   printf("(%d, %d), ", queries[i].first, queries[i].second);
  // }
  // printf("\n");
  static int qidx[100001];
  {
    int i = 0;
    for(int j = 0; j <= M; ++j) {
      while(i < Q && queries[i].first < j) ++i;
      qidx[j] = i;
    }
  }
  // printf("qidx = ");
  // for(int i = 0; i <= M; ++i) {
  //   printf("%d, ", qidx[i]);
  // }
  // printf("\n");
  static int lru_seq[100000];
  for(int i = 0; i < M; ++i) {
    lru_seq[i] = i;
  }
  sort(lru_seq, lru_seq+M, [&](int x, int y) -> bool {
      int xx = (qidx[x] == qidx[x+1]) ? ~x : queries[qidx[x+1]-1].second;
      int yy = (qidx[y] == qidx[y+1]) ? ~y : queries[qidx[y+1]-1].second;
      return xx < yy;
  });
  // printf("lru_seq = ");
  // for(int i = 0; i < M; ++i) {
  //   printf("%d, ", lru_seq[i]);
  // }
  // printf("\n");
  int max_ign = 1;
  while(max_ign < M && lru_seq[max_ign] <= lru_seq[max_ign-1]) ++max_ign;
  // printf("max_ign = %d\n", max_ign);
  static int max_times[100000];
  fill(max_times, max_times+N, Q);
  for(int i = M-1; i >= max_ign; --i) {
    int j = qidx[lru_seq[i]+1]-1;
    int min_j = qidx[lru_seq[i]];
    for(int k = 0; k < N; ++k) {
      while(j >= min_j && queries[j].second > max_times[k]) --j;
      if(j < min_j) {
        printf("No\n");
        return 0;
      }
      max_times[k] = queries[j].second;
      // printf("i=%d: max_times[%d] = %d\n", i, k, max_times[k]);
      --j;
    }
  }
  printf("Yes\n");
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:6:43: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   int N, M, Q; scanf("%d%d%d", &N, &M, &Q);
                                           ^
./Main.cpp:9:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &queries[i].first); --queries[i].first;
                                   ^

Judge Result