oj.uz

Submission #516628

# Submission time Handle Problem Language Result Execution time Memory
516628 2022-01-21T16:48:30 Z K4YAN Long Mansion (JOI17_long_mansion) C++17
100 / 100
 520 ms 48840 KB 
//Be Name Khoda

#include<bits/stdc++.h>
#pragma GCC optmize("Ofast,unroll-loops")
#pragma GCC target ("avx2,tune=native")

using namespace std;

#define ll long long
#define ld long double
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define pll pair<ll, ll>
#define plll pair<pll, ll>

const int mxn = 5e5 + 32;
int n, t, k, q;
int c[mxn], cnt[mxn];
pii ans[mxn];
vector<int> keys[mxn];

void input() {

    cin >> n;
    for(int i = 1; i < n; i++) {
        cin >> c[i];
    }
    for(int i = 1; i <= n; i++) {
        cin >> k;
        for(int j = 0; j < k; j++) {
            cin >> q;
            keys[i].push_back(q);
        }
    } cin >> t;

}

inline void merge(int l, int r, int m) {

    bool mark[r - l + 5];
    int tmp[r - l + 5];
    int pr = m, pl = m - 1;
    memset(mark, 0, sizeof(mark));
    memset(tmp, 0, sizeof(tmp));

    for(int i = m - 1; i > l - 1; i--) {
        for(auto u : keys[i]) cnt[u]++;
        while(pr < r) {
            if(cnt[c[pr - 1]] <= 0) {
                break;
            }
            if(cnt[c[pr - 1]] > 0) {
                for(auto u : keys[pr]) cnt[u]++;
                pr++;
            } 
        }
        tmp[i - l] = pr;
        if(i > l) {
            if(cnt[c[i - 1]] > 0) mark[i - l] = 1;
        }
    }
    for(int i = l; i < m; i++) {
        if(mark[i - l]) continue;
        if(ans[i].second >= m) {
            ans[i].second = tmp[i - l];
        }
        for(int j = i + 1; j < m; j++) {
            if(!mark[j - l]) break;
            if(ans[j].second < m) continue;
            ans[j].first = i, ans[j].second = tmp[i - l];
        }
    }

    for(int i = l; i < pr; i++) {
        for(auto u : keys[i]) cnt[u]--;
    }
    for(int i = m; i < r; i++) {
        for(auto u : keys[i]) cnt[u]++;
        while(pl > l - 1) {
            if(cnt[c[pl]] <= 0) {
                break;
            }
            if(cnt[c[pl]] > 0) {
                for(auto u : keys[pl]) cnt[u]++;
                pl--;
            }
        }
        tmp[i - l] = pl + 1;
        if(i < r - 1) {
            if(cnt[c[i]] > 0) mark[i - l] = 1;
        }
    }
    for(int i = r - 1; i > m - 1; i--) {
        if(mark[i - l]) continue;
        if(ans[i].first <= m) {
            ans[i].first = tmp[i - l];
        }
        for(int j = i - 1; j > m - 1; j--) {
            if(!mark[j - l]) break;
            if(ans[j].first > m) continue;
            ans[j].first = tmp[i - l], ans[j].second = i + 1;
        }
    }
    for(int i = pl + 1; i < r; i++) {
        for(auto u : keys[i]) cnt[u]--;
    }
    return;

}

void solve(int l, int r) {

    if(r - l <= 0) return;
    if(r - l == 1) {
        ans[l] = make_pair(l, r);
        return;
    }
    int m = (l + r) >> 1;
    solve(l, m); solve(m, r);
    merge(l, r, m);
    return;

}

int main() {

    ios::sync_with_stdio(false); cin.tie(NULL);

    input(), solve(1, n + 1);
    for(int i = 0; i < t; i++) {
        int x, y;
        cin >> x >> y;
        if(y < ans[x].first || ans[x].second <= y) {
            cout << "NO\n";
            continue;
        }
        cout << "YES\n";
    }
    return 0;

}

Compilation message

long_mansion.cpp:4: warning: ignoring '#pragma GCC optmize' [-Wunknown-pragmas]
    4 | #pragma GCC optmize("Ofast,unroll-loops")
      |

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12196 KB Output is correct
2 Correct 10 ms 12184 KB Output is correct
3 Correct 10 ms 12364 KB Output is correct
4 Correct 9 ms 12260 KB Output is correct
5 Correct 9 ms 12236 KB Output is correct
6 Correct 10 ms 12236 KB Output is correct
7 Correct 8 ms 12200 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12196 KB Output is correct
2 Correct 10 ms 12184 KB Output is correct
3 Correct 10 ms 12364 KB Output is correct
4 Correct 9 ms 12260 KB Output is correct
5 Correct 9 ms 12236 KB Output is correct
6 Correct 10 ms 12236 KB Output is correct
7 Correct 8 ms 12200 KB Output is correct
8 Correct 99 ms 18000 KB Output is correct
9 Correct 102 ms 17996 KB Output is correct
10 Correct 143 ms 18372 KB Output is correct
11 Correct 97 ms 18720 KB Output is correct
12 Correct 136 ms 17640 KB Output is correct
13 Correct 114 ms 18172 KB Output is correct
14 Correct 112 ms 18200 KB Output is correct
15 Correct 96 ms 18292 KB Output is correct
16 Correct 87 ms 18072 KB Output is correct
17 Correct 179 ms 18224 KB Output is correct
18 Correct 90 ms 18244 KB Output is correct
19 Correct 98 ms 18220 KB Output is correct
20 Correct 90 ms 18156 KB Output is correct
21 Correct 90 ms 18076 KB Output is correct
22 Correct 96 ms 18076 KB Output is correct
23 Correct 96 ms 17968 KB Output is correct
24 Correct 119 ms 18016 KB Output is correct
25 Correct 99 ms 18020 KB Output is correct
26 Correct 109 ms 18024 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 26480 KB Output is correct
2 Correct 281 ms 26232 KB Output is correct
3 Correct 285 ms 26056 KB Output is correct
4 Correct 335 ms 26428 KB Output is correct
5 Correct 288 ms 26356 KB Output is correct
6 Correct 206 ms 25012 KB Output is correct
7 Correct 207 ms 24832 KB Output is correct
8 Correct 195 ms 24892 KB Output is correct
9 Correct 200 ms 24900 KB Output is correct
10 Correct 201 ms 24856 KB Output is correct
11 Correct 221 ms 24836 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12196 KB Output is correct
2 Correct 10 ms 12184 KB Output is correct
3 Correct 10 ms 12364 KB Output is correct
4 Correct 9 ms 12260 KB Output is correct
5 Correct 9 ms 12236 KB Output is correct
6 Correct 10 ms 12236 KB Output is correct
7 Correct 8 ms 12200 KB Output is correct
8 Correct 99 ms 18000 KB Output is correct
9 Correct 102 ms 17996 KB Output is correct
10 Correct 143 ms 18372 KB Output is correct
11 Correct 97 ms 18720 KB Output is correct
12 Correct 136 ms 17640 KB Output is correct
13 Correct 114 ms 18172 KB Output is correct
14 Correct 112 ms 18200 KB Output is correct
15 Correct 96 ms 18292 KB Output is correct
16 Correct 87 ms 18072 KB Output is correct
17 Correct 179 ms 18224 KB Output is correct
18 Correct 90 ms 18244 KB Output is correct
19 Correct 98 ms 18220 KB Output is correct
20 Correct 90 ms 18156 KB Output is correct
21 Correct 90 ms 18076 KB Output is correct
22 Correct 96 ms 18076 KB Output is correct
23 Correct 96 ms 17968 KB Output is correct
24 Correct 119 ms 18016 KB Output is correct
25 Correct 99 ms 18020 KB Output is correct
26 Correct 109 ms 18024 KB Output is correct
27 Correct 283 ms 26480 KB Output is correct
28 Correct 281 ms 26232 KB Output is correct
29 Correct 285 ms 26056 KB Output is correct
30 Correct 335 ms 26428 KB Output is correct
31 Correct 288 ms 26356 KB Output is correct
32 Correct 206 ms 25012 KB Output is correct
33 Correct 207 ms 24832 KB Output is correct
34 Correct 195 ms 24892 KB Output is correct
35 Correct 200 ms 24900 KB Output is correct
36 Correct 201 ms 24856 KB Output is correct
37 Correct 221 ms 24836 KB Output is correct
38 Correct 392 ms 44368 KB Output is correct
39 Correct 456 ms 48840 KB Output is correct
40 Correct 387 ms 38508 KB Output is correct
41 Correct 520 ms 47440 KB Output is correct
42 Correct 193 ms 26172 KB Output is correct
43 Correct 239 ms 26108 KB Output is correct
44 Correct 294 ms 33764 KB Output is correct
45 Correct 275 ms 34060 KB Output is correct
46 Correct 349 ms 34280 KB Output is correct
47 Correct 196 ms 26416 KB Output is correct
48 Correct 209 ms 25924 KB Output is correct
49 Correct 354 ms 33524 KB Output is correct
50 Correct 309 ms 33788 KB Output is correct
51 Correct 345 ms 34616 KB Output is correct
52 Correct 241 ms 33064 KB Output is correct
53 Correct 355 ms 39816 KB Output is correct
54 Correct 345 ms 46744 KB Output is correct
55 Correct 377 ms 40100 KB Output is correct