Submission #234970

#	Time	Username	Problem	Language	Result	Execution time	Memory
234970		AlexLuchianov	Long Mansion (JOI17_long_mansion)	C++14	100 / 100	670 ms	94652 KiB

long_mansion

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <stack>

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 500000;
int const lgmax = 20;

vector<int> keys[5 + nmax];
int path[5 + nmax];
int firstleft[5 + nmax], firstright[5 + nmax];

namespace RMQ{
  int lg[1 + nmax];
  int rmq[1 + lgmax][1 + nmax];
  void initialize(int n){
    for(int i = 2; i <= n; i++)
      lg[i] = lg[i / 2] + 1;
    for(int i = 1;i <= n; i++)
      rmq[0][i] = firstleft[i];
    for(int h = 1; h <= lgmax; h++)
      for(int i = 1;i <= n - (1 << h) + 1; i++)
        rmq[h][i] = min(rmq[h - 1][i], rmq[h - 1][i + (1 << (h - 1))]);
  }

  int extract(int x, int y){
    int h = lg[y - x];
    return min(rmq[h][x], rmq[h][y - (1 << h) + 1]);
  }
}

map<int,int> frec;

void _addset(int room){
  for(int i = 0; i < keys[room].size(); i++)
    frec[keys[room][i]] = room;
}

int sol[1 + nmax][2];

void expandright(int &x, int &y, int n){
  for(int jump = (1 << 20); 0 < jump; jump /= 2)
    if(y + jump <= n && x <= RMQ::extract(y + 1, y + jump))
      y += jump;
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n;
  cin >> n;
  for(int i = 1;i < n; i++)
    cin >> path[i];
  for(int i = 1;i <= n; i++){
    int k;
    cin >> k;
    for(int j = 1;j <= k; j++){
      int val;
      cin >> val;
      keys[i].push_back(val);
    }
  }

  for(int i = 1; i <= n; i++) {
    firstleft[i] = frec[path[i - 1]];
    _addset(i);
  }
  frec.clear();

  for(int i = n; 1 <= i; i--){
    firstright[i] = frec[path[i]];
    if(firstright[i] == 0)
      firstright[i] = n + 1;
    _addset(i);
  }
  RMQ::initialize(n);

  for(int i = 1; i <= n; i++)
    sol[i][0] = sol[i][1] = i;

  stack<int> st;

  for(int i = 1; i <= n; i++){
    expandright(sol[i][0], sol[i][1], n);
    while(0 < st.size() && firstright[st.top()] <= sol[i][1]) {
      sol[i][0] = min(sol[i][0], sol[st.top()][0]);
      sol[i][1] = max(sol[i][1], sol[st.top()][1]);
      expandright(sol[i][0], sol[i][1], n);
      st.pop();
    }
    st.push(i);
  }

  int q;
  cin >> q;
  for(int i = 1; i <= q; i++){
    int x, y;
    cin >> x >> y;
    if(sol[x][0] <= y && y <= sol[x][1])
      cout << "YES\n";
    else
      cout << "NO\n";
  }
  return 0;
}

Compilation message (stderr)

long_mansion.cpp: In function 'void _addset(int)':
long_mansion.cpp:43:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < keys[room].size(); i++)
                  ~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 75 / 75