Submission #889199

#	Time	Username	Problem	Language	Result	Execution time	Memory
889199		dimashhh	Long Mansion (JOI17_long_mansion)	C++17	0 / 100	3022 ms	82116 KiB

long_mansion

#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({it,i});
        }
    }
}
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 << (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 (stderr)

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

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