QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#534953 | #8338. Quad Kingdoms Chess | liqingyang | RE | 0ms | 10740kb | C++17 | 2.2kb | 2024-08-27 17:56:41 | 2024-08-27 17:56:41 |
Judging History
answer
#include<iostream>
#include<random>
#include<vector>
using namespace std;
mt19937 Rand(20080704);
int n,m,q,a[2][100010];
vector<pair<int,int> > e[2][100010];
unsigned int R[100010],ans[200010];
struct node
{
int min1,min2,c;
unsigned int v;
};
struct tree
{
node a[400000];
inline void update(int p)
{
a[p].min1=min(a[p<<1].min1,a[(p<<1)|1].min1);
a[p].min2=min(a[p<<1].min1==a[p].min1?a[p<<1].min2:a[p<<1].min1
,a[(p<<1)|1].min1==a[p].min1?a[(p<<1)|1].min2:a[(p<<1)|1].min1);
}
inline void change(int p,int minn,int c,unsigned int v)
{
if(a[p].min1>minn)
{
return;
}
a[p].min1=a[p].c=c;
a[p].v^=v;
}
inline void pushdown(int p)
{
if(a[p].c)
{
change(p<<1,a[p].min1,a[p].c,a[p].v);
change((p<<1)|1,a[p].min1,a[p].c,a[p].v);
a[p].c=a[p].v=0;
}
}
void change(int l,int r,int ll,int rr,int v,int p)
{
if(r<ll||l>rr||v<a[p].min1)
{
return;
}
if(ll<=l&&r<=rr&&v<a[p].min2)
{
change(p,a[p].min1,v,R[v]);
return;
}
pushdown(p);
int mid=l+r>>1;
change(l,mid,ll,rr,v,p<<1);
change(mid+1,r,ll,rr,v,(p<<1)|1);
update(p);
}
void build(int l,int r,int p)
{
a[p].min1=0,a[p].min2=1e9;
a[p].c=a[p].v=0;
if(l==r)
{
return;
}
int mid=l+r>>1;
build(l,mid,p<<1);
build(mid+1,r,(p<<1)|1);
}
void query(int l,int r,int p)
{
if(l==r)
{
ans[l]^=a[p].v;
return;
}
pushdown(p);
int mid=l+r>>1;
query(l,mid,p<<1);
query(mid+1,r,(p<<1)|1);
}
};
inline void solve(int n,int *a,vector<pair<int,int> > *e)
{
static tree T;
T.build(1,q,1);
for(int i=n;i;i--)
{
int k=1,l=a[i];
for(int j=0;j<e[i].size();j++)
{
int t=e[i][j].first;
T.change(1,q,k,t-1,l,1);
k=t,l=e[i][j].second;
}
T.change(1,q,k,q,l,1);
}
T.query(1,q,1);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[0][i];
}
cin>>m;
for(int i=1;i<=m;i++)
{
cin>>a[1][i];
}
cin>>q;
for(int i=1,op,x,y;i<=q;i++)
{
cin>>op>>x>>y;
e[op-1][x].push_back({i,y});
}
for(int i=1;i<=1e5;i++)
{
R[i]=Rand();
}
solve(n,a[0],e[0]);
solve(m,a[1],e[1]);
for(int i=1;i<=q;i++)
{
puts(ans[i]?"NO":"YES");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 10740kb
input:
5 1 2 3 4 5 5 5 4 3 2 1 8 1 1 5 1 4 2 1 2 4 1 5 1 1 5 5 2 1 4 2 3 5 2 5 5
output:
NO NO NO YES NO NO NO YES
result:
ok 8 tokens
Test #2:
score: -100
Runtime Error
input:
1 2 6 2 1 1 1 1 1 200000 2 6 2 1 1 1 1 1 1 1 1 2 2 1 1 1 1 2 1 1 1 2 4 1 2 1 2 1 1 1 1 1 2 2 5 1 1 1 1 1 1 2 1 1 1 2 6 1 1 1 2 1 1 2 1 1 2 2 3 1 1 1 1 2 1 1 2 6 2 1 1 2 2 4 1 1 1 2 2 6 1 1 1 2 1 1 1 2 5 2 2 6 2 1 1 1 2 4 2 2 5 2 2 6 2 1 1 1 2 5 1 2 6 2 1 1 2 1 1 1 1 1 1 2 4 1 1 1 2 1 1 2 1 1 2 2 3 2...