Submission #1264119

#TimeUsernameProblemLanguageResultExecution timeMemory
1264119aihoiLong Mansion (JOI17_long_mansion)C++20
Compilation error
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; }

Compilation message (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];
      |                     ^