Submission #114057

#	Time	Username	Problem	Language	Result	Execution time	Memory
114057		popovicirobert	Long Mansion (JOI17_long_mansion)	C++14	5 / 100	3041 ms	13608 KiB

long_mansion

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

vector <char> lg;

inline int get_mx(int x, int y, vector < vector <int> > &rmq, vector <int> &arr) {
    int bit = lg[y - x + 1];
    return max(arr[rmq[x][bit]], arr[rmq[y - (1 << bit) + 1][bit]]);
}

inline int get_mn(int x, int y, vector < vector <int> > &rmq, vector <int> &arr) {
    int bit = lg[y - x + 1];
    return min(arr[rmq[x][bit]], arr[rmq[y - (1 << bit) + 1][bit]]);
}

vector <bool> sol;
int n, q;

inline void solve(vector <int> &c, vector < vector <int> > &key, vector < pair <int, int> > &qry) {

    vector <int> last(n + 1, -1), prv(n + 1, -1), nxt(n + 1, -1);
    int i;

    for(i = 1; i < n; i++) {
        for(auto it : key[i]) {
            last[it] = i;
        }
        prv[i + 1] = last[c[i]];
    }

    fill(last.begin(), last.end(), n + 1);

    for(i = n - 1; i >= 1; i--) {
        for(auto it : key[i + 1]) {
            last[it] = i + 1;
        }
        nxt[i] = last[c[i]];
    }

    /*vector < vector <int> > rmq(n + 1, vector <int>(19));
    for(i = 1; i <= n; i++) {
        rmq[i][0] = i;
    }

    for(int bit = 1; (1 << bit) <= n; bit++) {
        for(i = 1; i + (1 << bit) <= n + 1; i++) {
            int x = rmq[i][bit - 1], y = rmq[i + (1 << (bit - 1))][bit - 1];

            if(nxt[x] > nxt[y]) {
                rmq[i][bit] = x;
            }
            else {
                rmq[i][bit] = y;
            }
        }
    }

    vector <int> len(n + 1);

    for(i = 1; i <= n; i++) {
        if(prv[i] == -1) {
            len[i] = -1;
            continue;
        }

        int res = prv[i];
        for(int step = 1 << 18; step; step >>= 1) {
            if(res + step <= n && get_mx(prv[i], res + step, rmq, nxt) <= i) {
                res += step;
            }
        }

        len[i] = res + 1;
    }

    for(int bit = 1; (1 << bit) <= n; bit++) {
        for(i = 1; i + (1 << bit) <= n + 1; i++) {
            int x = rmq[i][bit - 1], y = rmq[i + (1 << (bit - 1))][bit - 1];

            if(len[x] < len[y]) {
                rmq[i][bit] = x;
            }
            else {
                rmq[i][bit] = y;
            }
        }
    }*/


    for(i = 1; i <= q; i++) {
        int x = qry[i].first, y = qry[i].second;

        if(x > y) {
            continue;
        }

        //sol[i] = (get_mn(x + 1, y, rmq, len) >= x);

        sol[i] = 1;
        for(int p = x + 1; p <= y && sol[i]; p++) {
            if(prv[p] == -1) {
                sol[i] = 0;
                break;
            }
            for(int j = prv[p]; j < x; j++) {
                if(nxt[j] >= p) {
                    sol[i] = 0;
                    break;
                }
            }
        }

    }
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;

    lg.resize(n + 1);
    for(i = 2; i <= n; i++) {
        lg[i] = lg[i >> 1] + 1;
    }

    vector <int> c(n);

    for(i = 1; i < n; i++) {
        cin >> c[i];
    }

    vector < vector <int> > key(n + 1);

    for(i = 1; i <= n; i++) {
        int x;
        cin >> x;

        while(x > 0) {
            x--;
            int id;
            cin >> id;
            key[i].push_back(id);
        }
    }

    cin >> q;

    vector < pair <int, int> > qry(q + 1);

    for(i = 1; i <= q; i++) {
        int x, y;
        cin >> x >> y;
        qry[i] = {x, y};
    }

    sol.resize(q + 1);

    solve(c, key, qry);

    for(i = 1; i <= q; i++) {
        qry[i].first = n - qry[i].first + 1;
        qry[i].second = n - qry[i].second + 1;
    }
    for(i = 1; i < n - i; i++) {
        swap(c[i], c[n - i]);
    }
    for(i = 1; i < n - i + 1; i++) {
        swap(key[i], key[n - i + 1]);
    }

    solve(c, key, qry);

    for(i = 1; i <= q; i++) {
        if(sol[i] == 0) {
            cout << "NO\n";
        }
        else {
            cout << "YES\n";
        }
    }

    //cin.close();
    //cout.close();
    return 0;
}

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