Submission #47427

#	Time	Username	Problem	Language	Result	Execution time	Memory
47427		qoo2p5	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	1089 ms	262144 KiB

long_mansion

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int INF = (int) 1e9 + 1e6;
const ll LINF = (ll) 1e18 + 1e9;
const ll MOD = (ll) 1e9 + 7;

#define sz(x) (int) (x).size()
#define mp(x, y) make_pair(x, y)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb(s, t, x) (int) (lower_bound(s, t, x) - s)
#define ub(s, t, x) (int) (upper_bound(s, t, x) - s)
#define rep(i, f, t) for (auto i = f; i < t; ++(i))
#define per(i, f, t) for (auto i = (f); i >= (t); --(i))

ll power(ll x, ll y, ll mod = MOD) {
    if (y == 0) {
        return 1;
    }
    if (y & 1) {
        return power(x, y - 1, mod) * x % mod;
    } else {
        ll tmp = power(x, y / 2, mod);
        return tmp * tmp % mod;
    }
}

template<typename A, typename B> bool mini(A &x, const B &y) {
    if (y < x) {
        x = y;
        return true;
    }
    return false;
}

template<typename A, typename B> bool maxi(A &x, const B &y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

void add(ll &x, ll y) {
    x += y;
    if (x >= MOD) x -= MOD;
    if (x < 0) x += MOD;
}

void run();

#define TASK ""

int main() {
#ifdef LOCAL
    if (strlen(TASK) > 0) {
        cerr << "Reminder: you are using file i/o, filename: " TASK "!" << endl << endl;
    }
#endif
#ifndef LOCAL
    if (strlen(TASK)) {
        freopen(TASK ".in", "r", stdin);
        freopen(TASK ".out", "w", stdout);
    }
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#endif
    cout << fixed << setprecision(12);
    run();
    return 0;
}

// == SOLUTION == //

const int N = 1 << 19;

int n, q;
int c[N];
vector<int> what[N];
vector<int> color[N];
int L[N], R[N];

struct Q {
    int x, y, id;
};

bool ans[N];
Q qu[N];

int tree[2 * N];
int val[N];

void upd(int i, int val) {
    i += N;
    tree[i] = val;
    i /= 2;
    while (i > 0) {
        tree[i] = max(tree[2 * i], tree[2 * i + 1]);
        i /= 2;
    }
}

int get(int i, int tl, int tr, int l, int r) {
    if (tl >= r || tr <= l) {
        return -INF;
    }
    if (l <= tl && tr <= r) return tree[i];
    int tm = (tl + tr) / 2;
    return max(get(2 * i, tl, tm, l, r), get(2 * i + 1, tm, tr, l, r));
}

int find(int i, int tl, int tr, int l, int r, int val) {
    if (tl >= r || tr <= l) {
        return N;
    }
    int tm = (tl + tr) / 2;
    if (l <= tl && tr <= r) {
        if (tree[i] <= val) {
            return N;
        }
        if (tl == tr - 1) {
            return tl;
        }
        if (tree[2 * i] > val) {
            return find(2 * i, tl, tm, l, r, val);
        } else {
            return find(2 * i + 1, tm, tr, l, r, val);
        }
    }
    int res = find(2 * i, tl, tm, l, r, val);
    if (res != N) {
        return res;
    }
    return find(2 * i + 1, tm, tr, l, r, val);
}

void run() {
    cin >> n;
    rep(i, 0, n - 1) {
        cin >> c[i];
    }
    rep(i, 0, n) {
        int k;
        cin >> k;
        rep(j, 0, k) {
            int v;
            cin >> v;
            what[i].pb(v);
        }
    }
    cin >> q;
    rep(i, 0, q) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        qu[i] = {x, y, i};
    }
    
    rep(iter, 0, 2) {
        rep(i, 0, N) color[i].clear();
        rep(i, 0, N) color[i].pb(-INF);
        rep(i, 0, n) {
            for (int j : what[i]) {
                color[j].pb(i);
            }
        }
        rep(i, 0, N) color[i].pb(INF);
        
        L[0] = INF;
        R[n - 1] = -INF;
        rep(i, 0, n - 1) {
            int w = c[i];
            L[i + 1] = *lower_bound(all(color[w]), i + 1);
            R[i] = *(--lower_bound(all(color[w]), i + 1));
        }
        rep(i, 0, n) {
            upd(i, L[i]);
        }
        rep(i, 0, n) {
            val[i] = find(1, 0, N, R[i] + 1, i + 1, i);
        }
        rep(i, 0, n) {
            upd(i, -val[i]);
        }
        rep(i, 0, q) {
            if (qu[i].x < qu[i].y) {
                ans[qu[i].id] = -get(1, 0, N, qu[i].x, qu[i].y) > qu[i].x;
            }
        }
        
        per(i, n - 1, 0) {
            c[i] = c[i - 1];
        }
        reverse(c, c + n);
        reverse(what, what + n);
        rep(i, 0, q) {
            qu[i].x = n - 1 - qu[i].x;
            qu[i].y = n - 1 - qu[i].y;
        }
    }
    
    rep(i, 0, q) {
        cout << (ans[i] ? "YES" : "NO") << "\n";
    }
}

Compilation message (stderr)

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(TASK ".in", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
long_mansion.cpp:68:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(TASK ".out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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