| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1299533 | lizi14 | Obstacles for a Llama (IOI25_obstacles) | C++20 | 0 ms | 0 KiB |
//#include "obstacles.h"
#include <cassert>
#include <cstdio>
//#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
vector<int>k;
vector<int>h;
int x[3][N];
int ixvi[3][N];
long long n,bati;
//const int N=2e5+5;
vector<int>v[N];
vector<pair<int,int>>p;
void make_set(int w){
p[w].first=w;
p[w].second=1;
// parent[v]=v;
// size[v]=1;
}
pair<int,int>rec(int w){
if(w!=p[w].first) {
int len=p[w].second;
p[w]=rec(p[w].first);
p[w].second+=len;
}
return p[w];
}
void gaertianeba(int u,int w){
int k=rec(u).first;
int h=rec(w).first;
if(k!=h){
if(v[k].size()>=v[h].size()){
//v[k].push_back(h);
p[k].second+=v[h].size();
p[h].first=k;
}
else{
//v[h].push_back(k);
p[h].second+=v[k].size();
p[k].first=h;
}
}
return;
}
void initialize(vector<int> T, vector<int> H) {
n=H.size();
int j=0;
bati=T.size();
for(int j=0; j<H.size(); j++){
if(T[0]<=H[j]){
//x[j]=-1;
k.push_back(j);
}
else{
//x[j]=1;
}
//cout<<x[j]<<" ";
//x[j]=a;
//j++;
}
for(int i=0; i<H.size(); i++){
if(T[bati-1]<=H[i]){
h.push_back(i);
//x[i]=-1;
}
}
if(bati==3){
for(int i=0; i<3; i++){
for(int j=0; j<n; j++){
x[i][j]=i*n+j;
if(T[i]<=H[j]){
ixvi[i][j]=-1;
}
else ixvi[i][j]=1;
}
}
}
return;
}
bool can_reach(int L, int R, int S, int D) {
//L--,R--,S--,D--;
if(S>D)swap(S,D);
if(bati==1){
auto it=lower_bound(k.begin(),k.end(),S);
if(it!=k.end() && *it<D){
return false;
}
//if(lower_bound(k.begin(),k.end(),S)<D)return 0;
else return true;
}
else if(bati==3){
for(int i=0; i<bati; i++){
for(int j=0; j<n; j++){
make_set(x[i][j]);
}
}
for(int i=0; i<bati; i++){
for(int j=0; j<n; j++){
if(ixvi[i][j]!=-1){
if(i>0){
if(ixvi[i-1][j]!=-1){
gaertianeba(x[i-1][j],x[i][j]);
}
}
if(j>0){
if(ixvi[i][j-1]!=-1){
gaertianeba(x[i][j-1],x[i][j]);
}
}
}
}
}
int k=rec(S).first;
int h=rec(D).first;
if(k==h){
return true;
}
else{
return 0;
}
}
else{
auto it=lower_bound(h.begin(),h.end(),S);
if(it!=h.end() && *it<D){
return false;
}
//if(lower_bound(k.begin(),k.end(),S)<D)return 0;
else return true;
}
}
int main() {
int N, M;
assert(2 == scanf("%d %d", &N, &M));
std::vector<int> T(N), H(M);
for (int i = 0; i < N; i++)
assert(1 == scanf("%d", &T[i]));
for (int i = 0; i < M; i++)
assert(1 == scanf("%d", &H[i]));
int Q;
assert(1 == scanf("%d", &Q));
std::vector<int> L(Q), R(Q), S(Q), D(Q);
for (int i = 0; i < Q; i++)
assert(4 == scanf("%d %d %d %d", &L[i], &R[i], &S[i], &D[i]));
fclose(stdin);
std::vector<bool> A(Q);
initialize(T, H);
for (int i = 0; i < Q; i++)
A[i] = can_reach(L[i], R[i], S[i], D[i]);
for (int i = 0; i < Q; i++)
if (A[i])
printf("1\n");
else
printf("0\n");
fclose(stdout);
return 0;
}