Submission #397186

#	Time	Username	Problem	Language	Result	Execution time	Memory
397186		parsabahrami	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	606 ms	150272 KiB

long_mansion

/* There's someone in my head but it's not me */ 
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 5e5 + 10, MOD = 1e9 + 7;
int gl[N], gr[N], ml[N], mr[N], nl[N], nr[N], lst[N], A[N], C[N], n, q; vector<int> B[N];
template <class func> struct node {
    int x; node *lc, *rc; func cmp;

    node() : x(0), lc(nullptr), rc(nullptr) {};

    void build(int l = 1, int r = n) {
        if (r - l < 2) return;
        lc = new node<func>();
        rc = new node<func>(); 
        int md = (l + r) >> 1;
        lc->build(l, md), rc->build(md, r);
    }    

    void modify(int p, int y, int l = 1, int r = n) {
        if (r - l < 2) { x = y; return; }
        int md = (l + r) >> 1;
        if (p < md) lc->modify(p, y, l, md);
        else rc->modify(p, y, md, r);
        x = cmp(lc->x, rc->x) ? lc->x : rc->x;
    }

    int get(int ql, int qr, int l = 1, int r = n) {
        if (qr <= l || r <= ql) return cmp(1, 0) ? 0 : n + 1;
        if (ql <= l && r <= qr) return x;
        int md = (l + r) >> 1;
        int a = lc->get(ql, qr, l, md), b = rc->get(ql, qr, md, r);
        return cmp(a, b) ? a : b;
    }
};
node<greater<>> *mx;
node<less<>> *mn;

int main() {
    mx = new node<greater<>>();
    mn = new node<less<>>();
    scanf("%d", &n);
    for (int i = 1; i < n; i++) 
        scanf("%d", &C[i]);
    for (int i = 1, t, x; i <= n; i++) {
        for (scanf("%d", &t); t; t--) 
            scanf("%d", &x), B[i].push_back(x);
    }
    mx->build(), mn->build();
    for (int i = 1; i < n; i++) {
        for (int &x : B[i]) lst[x] = i;
        mn->modify(i, gl[i] = lst[C[i]]);
    }
    fill(lst, lst + N, n + 1);
    for (int i = n - 1; i; i--) {
        for (int &x : B[i + 1]) lst[x] = i + 1;
        mx->modify(i, gr[i] = lst[C[i]]);
    }   
    for (int i = n - 1; i; i--) {
        for (nr[i] = i + 1; nr[i] < n && gl[i] <= gl[nr[i]]; nr[i] = nr[nr[i]]);
    }
    for (int i = 1; i < n; i++) {
        for (nl[i] = i - 1; nl[i] && gr[i] >= gr[nl[i]]; nl[i] = nl[nl[i]]);
    }
    for (int i = 1; i <= n; i++) {
        ml[i] = mr[i] = i;
        for (;;) {
            if (ml[i] > 1 && gr[ml[i] - 1] <= mr[i])
                mr[i] = max(mr[i], mr[ml[i] - 1]), ml[i] = ml[ml[i] - 1];
            else if (mr[i] < n && gl[mr[i]] >= ml[i]) 
                mr[i]++;
            else break;
        }
    }  
    for (scanf("%d", &q); q; q--) {
        int x, y; scanf("%d%d", &x, &y);
        if (x < y) printf(mr[x] >= y ? "YES\n" : "NO\n");
        else printf(ml[x] <= y ? "YES\n" : "NO\n");
    }
    return 0;
}

Compilation message (stderr)

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   50 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
long_mansion.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |         scanf("%d", &C[i]);
      |         ~~~~~^~~~~~~~~~~~~
long_mansion.cpp:54:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |         for (scanf("%d", &t); t; t--)
      |              ~~~~~^~~~~~~~~~
long_mansion.cpp:55:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |             scanf("%d", &x), B[i].push_back(x);
      |             ~~~~~^~~~~~~~~~
long_mansion.cpp:83:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   83 |     for (scanf("%d", &q); q; q--) {
      |          ~~~~~^~~~~~~~~~
long_mansion.cpp:84:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |         int x, y; scanf("%d%d", &x, &y);
      |                   ~~~~~^~~~~~~~~~~~~~~~

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