QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#721775 | #8338. Quad Kingdoms Chess | AnotherDayofSun# | WA | 14ms | 20088kb | C++14 | 2.4kb | 2024-11-07 16:48:11 | 2024-11-07 16:48:11 |
Judging History
answer
#include<bits/stdc++.h>
#define For(i,j,k) for(int i=(j);i<=(k);i++)
#define re
#define vi vector<int>
#define pb push_back
#define ll long long
#define P 998244353
using namespace std;
inline int read(){
re char c;int res=0;bool flag=0;
while(c=getchar(),c<48)(c=='-')&&(flag=1);
do res=(res<<3)+(res<<1)+(c^48);
while(c=getchar(),c>47);
flag&&(res=-res);
return res;
}
const int MN=1e5+5;
int n,a[MN];
struct ds {
static const int N=MN<<2;
#define ls (k<<1)
#define rs (k<<1|1)
#define mid ((l+r)>>1)
int mx[N],cnt[N];
ll sum[N],ans[N];
void qry2(int k,int l,int r,int &tcnt,ll &tsum,ll &tans,int nowmx) {
if(l==r) {
if(mx[k]>=nowmx) tcnt=cnt[k],tsum=sum[k],tans=ans[k];
else tcnt=0,tsum=0,tans=0;
return;
}
if(mx[rs]>=nowmx) {
qry2(rs,mid+1,r,tcnt,tsum,tans,nowmx);
int lcnt=cnt[k]-cnt[rs];
int lsum=sum[k]-sum[rs];
int lans=(ans[k]-ans[rs])-lsum*cnt[rs];
tcnt+=lcnt,tsum+=lsum,tans+=lans;
} else qry2(ls,l,mid,tcnt,tsum,tans,nowmx);
}
void pushup(int k,int l,int r) {
mx[k]=max(mx[ls],mx[rs]);
if(mx[rs]>mx[ls]) cnt[k]=cnt[rs],sum[k]=sum[rs],ans[k]=ans[rs];
else {
int tcnt; ll tsum,tans;
qry2(ls,l,mid,tcnt,tsum,tans,mx[rs]);
cnt[k]=tcnt+cnt[rs],sum[k]=tsum+sum[rs],ans[k]=tans+tsum*cnt[rs]+ans[rs];
}
}
void upd(int k,int l,int r,int p,int v) {
if(l==r) {
mx[k]=sum[k]=ans[k]=v;
cnt[k]=1;
return;
}
if(p<=mid) upd(ls,l,mid,p,v);
else upd(rs,mid+1,r,p,v);
pushup(k,l,r);
}
void build(int k,int l,int r,int *a) {
if(l==r) {
mx[k]=sum[k]=ans[k]=a[l];
cnt[k]=1;
return;
}
build(ls,l,mid,a),build(rs,mid+1,r,a);
pushup(k,l,r);
}
pair<ll,int> qry() {
return make_pair(ans[1],cnt[1]);
}
#undef mid
};
struct tpw {
static const int N=4e5+5;
int n,a[N]; ds t;
void rd() {
n=read();
For(i,1,n) a[i]=read();
t.build(1,1,n,a);
}
void mdf(int x,int y) {
a[x]=y;
t.upd(1,1,n,x,y);
}
pair<ll,int> qry() {
return t.qry();
}
} line[2];
void works() {
line[0].rd();
line[1].rd();
int m=read();
while(m--) {
int o=read(),x=read(),y=read();
line[o-1].mdf(x,y);
// cerr<<line[0].qry().first<<' '<<line[1].qry().first<<endl;
if(line[0].qry()==line[1].qry()) printf("YES\n");
else printf("NO\n");
}
}
signed main() {
int T=1;
while(T--) {
works();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 18020kb
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: 0
Accepted
time: 11ms
memory: 20068kb
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...
output:
NO NO NO NO YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO N...
result:
ok 200000 tokens
Test #3:
score: 0
Accepted
time: 10ms
memory: 18032kb
input:
6 2 1 1 2 1 2 1 1 200000 2 1 1 1 1 2 1 1 1 2 1 2 2 1 1 2 1 1 2 1 2 2 1 2 1 1 2 1 3 1 1 6 2 1 5 2 1 4 2 1 3 1 2 1 2 1 4 2 1 4 2 2 1 2 2 1 2 1 3 1 1 6 1 1 1 2 2 1 1 1 6 1 1 3 1 1 5 2 1 6 2 1 5 2 2 1 2 1 2 1 1 5 2 2 1 1 2 1 1 1 6 1 2 1 2 2 1 1 1 3 2 2 1 1 1 6 1 1 4 2 1 2 1 1 1 1 2 1 1 1 2 1 1 6 2 1 6 2...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...
result:
ok 200000 tokens
Test #4:
score: -100
Wrong Answer
time: 14ms
memory: 20088kb
input:
6 1 3 1 2 1 2 6 2 1 3 3 3 1 200000 2 4 2 1 2 1 1 6 2 2 3 2 1 1 1 1 6 2 1 6 2 1 3 2 2 6 1 2 4 3 1 1 2 2 5 2 2 6 2 2 3 1 1 4 3 1 3 1 2 5 2 2 4 2 2 1 3 1 1 1 2 2 2 2 4 2 1 5 3 1 6 3 2 6 3 1 5 3 2 5 3 2 4 1 2 4 2 1 1 2 1 6 1 2 6 1 1 2 3 1 1 3 1 1 1 2 6 3 2 4 1 1 4 2 2 2 1 1 3 1 1 1 3 1 1 3 1 4 3 1 3 3 2...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...
result:
wrong answer 27th words differ - expected: 'YES', found: 'NO'