oj.uz

Submission #889202

# Submission time Handle Problem Language Result Execution time Memory
889202 2023-12-19T07:36:02 Z dimashhh Long Mansion (JOI17_long_mansion) C++17
5 / 100
 3000 ms 80356 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 1, MOD = 998244353;
typedef long long ll;

int n,q,c[N],b[N];
vector<array<int,3>> res(N);
vector<int> a[N];
int used[N],timer = 0,mind[N];
unordered_map<int,int> is[N];
vector<pair<int,int>> all;
void go(int l,int r){
    if(l >= r) return;
    int mid = (l + r) >> 1;
    go(l,mid);
    go(mid + 1,r);
    timer++;
    int it = mid;
    for(int j:a[it]){
        used[j] = timer;
    }
    for(int i = mid + 1;i <= r;i++){
        for(int j:a[i]){
            used[j] = timer;
        }
        while(it >= l && used[c[it - 1]] == timer){
            it--;
            for(int j:a[it]){
                used[j] = timer;
            }
        }
        if(used[c[i]] == timer) continue;
        if(it >= l){
            all.push_back({it,i});
        }
    }
    timer++;
    it = mid + 1;
    for(int j:a[it]){
        used[j] = timer;
    }
    for(int i = mid;i >= l;i--){
        for(int j:a[i]){
            used[j] = timer;
        }
        while(it <= r && used[c[it]] == timer){
            it++;
            for(int j:a[it]){
                used[j] = timer;
            }
        }
        if(used[c[i - 1]] == timer) continue;
        if(it <= r){
            all.push_back({i,it});
            // cout << it << ' ' << i << '\n';
        }
    }
}
void test(){
    cin >> n;
    for(int i = 1;i <= n - 1;i++){
        cin >> c[i];
    }
    for(int i = 1;i <= n;i++){
        mind[i] = 1e9;
        cin >> b[i];
        for(int j = 1;j <=b[i];j++){
            int x;
            cin >> x;
            is[i][x] = 1;
            a[i].push_back(x);
        }
        if(!is[i].count(c[i]) && !is[i].count(c[i - 1])){
            mind[i] = 1;
            array<int,3> f;
            f = {1,i,i};
            res[i] = f;
            all.push_back({i,i});
        }
    }
    all.push_back({1,n});
    go(1,n);
    for(int i = 1;i <=n;i++){
        // cout << res[i][0] << ' ' << res[i][1] << ' ' << res[i][2] << '\n';
    }
    int q;
    cin >> q;
    while(q--){
        int x,y;
        cin >> x >> y;
        int d = 1e9,l,r;
        for(auto [X,Y]:all){
            if(x > Y || x < X) continue;
            if(Y - X + 1 < d){
                d = Y - X + 1;
                l = X;
                r = Y;
            }
        }
        // cout << l << ' ' << r << '\n';
        cout << (y >= l && y <= r ? "YES\n":"NO\n");
    }
}
main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1; // cin >> T;
    while (T--)
        test();
}

Compilation message

long_mansion.cpp:104:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  104 | main()
      | ^~~~
long_mansion.cpp: In function 'void test()':
long_mansion.cpp:101:25: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
  101 |         cout << (y >= l && y <= r ? "YES\n":"NO\n");
      |                  ~~~~~~~^~~~~~~~~
long_mansion.cpp:101:51: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
  101 |         cout << (y >= l && y <= r ? "YES\n":"NO\n");
      |                                                   ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 50008 KB Output is correct
2 Correct 33 ms 50268 KB Output is correct
3 Correct 32 ms 50524 KB Output is correct
4 Correct 20 ms 50012 KB Output is correct
5 Correct 13 ms 50012 KB Output is correct
6 Correct 14 ms 50048 KB Output is correct
7 Correct 105 ms 50304 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 50008 KB Output is correct
2 Correct 33 ms 50268 KB Output is correct
3 Correct 32 ms 50524 KB Output is correct
4 Correct 20 ms 50012 KB Output is correct
5 Correct 13 ms 50012 KB Output is correct
6 Correct 14 ms 50048 KB Output is correct
7 Correct 105 ms 50304 KB Output is correct
8 Correct 2387 ms 56024 KB Output is correct
9 Execution timed out 3104 ms 55980 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3048 ms 80356 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 50008 KB Output is correct
2 Correct 33 ms 50268 KB Output is correct
3 Correct 32 ms 50524 KB Output is correct
4 Correct 20 ms 50012 KB Output is correct
5 Correct 13 ms 50012 KB Output is correct
6 Correct 14 ms 50048 KB Output is correct
7 Correct 105 ms 50304 KB Output is correct
8 Correct 2387 ms 56024 KB Output is correct
9 Execution timed out 3104 ms 55980 KB Time limit exceeded
10 Halted 0 ms 0 KB -