oj.uz

Submission #114057

# Submission time Handle Problem Language Result Execution time Memory
114057 2019-05-29T18:19:39 Z popovicirobert Long Mansion (JOI17_long_mansion) C++14
5 / 100
 3000 ms 13608 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(), 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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 8 ms 768 KB Output is correct
4 Correct 4 ms 640 KB Output is correct
5 Correct 8 ms 640 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 176 ms 640 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 8 ms 768 KB Output is correct
4 Correct 4 ms 640 KB Output is correct
5 Correct 8 ms 640 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 176 ms 640 KB Output is correct
8 Correct 139 ms 10364 KB Output is correct
9 Correct 118 ms 10436 KB Output is correct
10 Correct 274 ms 10680 KB Output is correct
11 Correct 465 ms 11236 KB Output is correct
12 Correct 166 ms 9976 KB Output is correct
13 Correct 111 ms 10616 KB Output is correct
14 Correct 117 ms 10620 KB Output is correct
15 Correct 244 ms 10488 KB Output is correct
16 Correct 493 ms 10488 KB Output is correct
17 Correct 119 ms 10488 KB Output is correct
18 Correct 130 ms 10624 KB Output is correct
19 Correct 153 ms 10728 KB Output is correct
20 Correct 386 ms 10488 KB Output is correct
21 Correct 483 ms 10412 KB Output is correct
22 Correct 264 ms 10488 KB Output is correct
23 Execution timed out 3027 ms 8840 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1335 ms 13592 KB Output is correct
2 Correct 2787 ms 13608 KB Output is correct
3 Execution timed out 3041 ms 12456 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 8 ms 768 KB Output is correct
4 Correct 4 ms 640 KB Output is correct
5 Correct 8 ms 640 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 176 ms 640 KB Output is correct
8 Correct 139 ms 10364 KB Output is correct
9 Correct 118 ms 10436 KB Output is correct
10 Correct 274 ms 10680 KB Output is correct
11 Correct 465 ms 11236 KB Output is correct
12 Correct 166 ms 9976 KB Output is correct
13 Correct 111 ms 10616 KB Output is correct
14 Correct 117 ms 10620 KB Output is correct
15 Correct 244 ms 10488 KB Output is correct
16 Correct 493 ms 10488 KB Output is correct
17 Correct 119 ms 10488 KB Output is correct
18 Correct 130 ms 10624 KB Output is correct
19 Correct 153 ms 10728 KB Output is correct
20 Correct 386 ms 10488 KB Output is correct
21 Correct 483 ms 10412 KB Output is correct
22 Correct 264 ms 10488 KB Output is correct
23 Execution timed out 3027 ms 8840 KB Time limit exceeded
24 Halted 0 ms 0 KB -