oj.uz

답안 #535968

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
535968 2022-03-12T02:21:50 Z cig32 Long Mansion (JOI17_long_mansion) C++17
0 / 100
 3000 ms 19196 KB 
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
#define int long long
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) { 
  if(p==0) return 1;
  int r = bm(b, p/2);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
int inv(int b) {
  return bm(b, MOD-2);
}
int f[MAXN];
int nCr(int n, int r) { 
  int ans = f[n]; ans *= inv(f[r]); ans %= MOD;
  ans *= inv(f[n-r]); ans %= MOD; return ans;
}

void precomp() { 
  f[0] = 1;
  for(int i=1; i<MAXN; i++) f[i] = (f[i-1] * i) % MOD;
}

void solve(int tc) {
  int n;
  cin >> n;
  int c[n];
  vector<int> sad[n + 1];
  for(int i=1; i<=n; i++) sad[i].push_back(0);
  for(int i=1; i<n; i++) {
    cin >> c[i];
    sad[c[i]].push_back(i);
  }
  for(int i=1; i<=n; i++) sad[i].push_back(n);
  vector<int> wow[n + 1];
  for(int i=1; i<=n; i++) {
    int x; cin >> x;
    for(int j=0; j<x; j++) {
      int y; cin >> y;
      wow[y].push_back(i);
    }
  }
  /*
  for(int i=1; i<=n; i++) {
    cout << "wow[" << i << "] = [";
    for(int j=0; j<wow[i].size(); j++) {
      cout << wow[i][j] << ",]"[j == wow[i].size() - 1];
      if(wow[i].size() - 1 != j) cout << " ";
    }
    if(wow[i].empty()) cout << "]";
    cout << "\n";
  }
  */
  int l[n+1], r[n+1];
  for(int i=1; i<=n; i++) l[i] = 1, r[i] = n;
  for(int i=1; i<=n; i++) {
    //cout << "i = " << i << ", sad[" << i << "].size = " << sad[i].size() << "\n";
    for(int j=1; j<sad[i].size(); j++) {
      // if nothing in [range]
      int lwb;
      if(wow[i].empty()) lwb = MOD;
      else if(wow[i][wow[i].size() - 1] < sad[i][j-1] + 1) lwb = MOD;
      else lwb = *lower_bound(wow[i].begin(), wow[i].end(), sad[i][j-1] + 1);
      //cout << "lower_bound(wow[" << i << "], " << sad[i][j-1] + 1 << ") = " << lwb << "\n";
      if(lwb > sad[i][j]) {
        // update range
        //cout << "range update " << sad[i][j-1]  +1 << ' ' << sad[i][j] <<"\n";
        for(int k=sad[i][j-1] + 1; k <= sad[i][j]; k++) l[k] = max(l[k], sad[i][j-1] + 1);
        for(int k=sad[i][j-1] + 1; k <= sad[i][j]; k++) r[k] = min(r[k], sad[i][j]);
      }
    }
  }
  int q;
  cin >> q;
  while(q--) {
    int x, y;
    cin >> x >> y;
    cout << (l[x] <= y && y <= r[x] ? "YES\n" : "NO\n");
  }
}
int32_t main(){
  precomp();
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}

Compilation message

long_mansion.cpp: In function 'void solve(long long int)':
long_mansion.cpp:64:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(int j=1; j<sad[i].size(); j++) {
      |                  ~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 2260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 2260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3070 ms 19196 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 2260 KB Output isn't correct
2 Halted 0 ms 0 KB -