oj.uz

Submission #114044

# Submission time Handle Problem Language Result Execution time Memory
114044 2019-05-29T17:35:53 Z popovicirobert Long Mansion (JOI17_long_mansion) C++14
0 / 100
 3000 ms 24188 KB 
#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(), -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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 896 KB Output is correct
2 Correct 7 ms 1024 KB Output is correct
3 Correct 10 ms 1408 KB Output is correct
4 Incorrect 4 ms 768 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 896 KB Output is correct
2 Correct 7 ms 1024 KB Output is correct
3 Correct 10 ms 1408 KB Output is correct
4 Incorrect 4 ms 768 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1364 ms 24188 KB Output is correct
2 Correct 2764 ms 24184 KB Output is correct
3 Execution timed out 3052 ms 23856 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 896 KB Output is correct
2 Correct 7 ms 1024 KB Output is correct
3 Correct 10 ms 1408 KB Output is correct
4 Incorrect 4 ms 768 KB Output isn't correct
5 Halted 0 ms 0 KB -