제출 #1264119

#제출 시각아이디문제언어결과실행 시간메모리
1264119aihoiLong Mansion (JOI17_long_mansion)C++20
컴파일 에러
0 ms0 KiB
#include<bits/stdc++.h>
#include<algorithm>
#include<random>
#include<chrono>
#include<cstdlib>
#include<ctime>
#include<numeric>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<iomanip>
#define int long long
#define ll long long
#define L LLONG_MAX
#define fi first
#define se second
#define pii pair<int,int>
#define sz(a) ((int)a.size())
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define REP(i,k,j) for(int i=k;i>=j;i--)
#define FORD(i,a) for(auto i:a)
using namespace std;

const int NMAX = 500000 + 5; // sửa tuỳ bài; JOI limit up to 5e5
int n,q;
int c[NMAX];
vector<int> a[NMAX];
vector<int> pos[NMAX]; // pos[type] = sorted list of rooms that chứa key "type"
int lef[NMAX], rig[NMAX];

bool inside(int l, int r, int key){
    if (key <= 0 || key >= NMAX) return false;
    auto &v = pos[key];
    if (v.empty()) return false;
    auto it = lower_bound(v.begin(), v.end(), l);
    return it!=v.end() && *it <= r;
}

void input(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if(!(cin>>n)) exit(0);
    FOR(i,1,n-1) cin>>c[i];
    FOR(i,1,n){
        int b; cin>>b;
        a[i].resize(b);
        FOR(j,0,b-1) {
            cin>>a[i][j];
            if (a[i][j] >= 0 && a[i][j] < NMAX) pos[a[i][j]].push_back(i);
        }
    }
    // pos[*] are filled in increasing room order already (we pushed i ascending),
    // so they are sorted -> no need to sort again.
    cin>>q;
}

void solve(){
    // compute lef/rig for each starting room i (1..n)
    FOR(i,1,n){
        lef[i]=rig[i]=i;
        bool nxt = true;
        while(nxt){
            nxt = false;
            // try extend left by checking corridor (lef[i]-1) if exists
            while (lef[i] > 1 && inside(lef[i], rig[i], c[lef[i]-1]) ){
                // when extend left into (lef[i]-1), we can merge with precomputed segment of lef[i]-1
                int L = lef[lef[i]-1];
                int R = rig[lef[i]-1];
                // update segment
                lef[i] = L;
                if (R > rig[i]) rig[i] = R;
                nxt = true;
            }
            // try extend right by checking corridor rig[i]
            // Note: use if (rig[i] < n) to avoid out-of-bound c[n]
            while (rig[i] < n && inside(lef[i], rig[i], c[rig[i]])){
                rig[i]++; // include room rig[i]
                // after including new room rig[i], there could be previous computed info if rig[i] <= i? 
                // But we only have lef/rig for indices < current i guaranteed; if rig[i] <= i nothing to merge.
                // However if we moved rig[i] to some j < i that has been computed, we can merge:
                if (rig[i] < i){
                    // merge with its precomputed block
                    if (lef[rig[i]] < lef[i]) lef[i] = lef[rig[i]];
                    if (rig[rig[i]] > rig[i]) rig[i] = rig[rig[i]];
                }
                nxt = true;
            }
            // one more attempt: maybe after right expansion we can again extend left via merged info
            // the outer while(nxt) takes care of repeating until stable
        }
    }

    // answer queries
    while(q--){
        int x,y; cin>>x>>y;
        if (x<=y){
            if (lef[x] <= y && y <= rig[x]) cout<<"YES\n"; else cout<<"NO\n";
        }else{
            // if x > y, since segments are contiguous, check same condition (we still computed lef[x],rig[x])
            if (lef[x] <= y && y <= rig[x]) cout<<"YES\n"; else cout<<"NO\n";
        }
    }
}

signed main(){
    input();
    solve();
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

long_mansion.cpp: In function 'void solve()':
long_mansion.cpp:16:11: error: expected unqualified-id before numeric constant
   16 | #define L LLONG_MAX
      |           ^~~~~~~~~
long_mansion.cpp:69:21: note: in expansion of macro 'L'
   69 |                 int L = lef[lef[i]-1];
      |                     ^