QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#385192 | #8338. Quad Kingdoms Chess | triple_dogs# | ML | 38ms | 16168kb | C++14 | 2.2kb | 2024-04-10 16:19:42 | 2024-04-10 16:19:42 |
Judging History
answer
#include<bits/stdc++.h>
#define MAXN 100005
#define BASE 19990303
#define MOD1 1000000007
#define MOD2 998244353
#define F first
#define S second
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> P;
mt19937_64 wcy(time(NULL));
ull pw[MAXN];
int n[2],m,a[2][MAXN];
struct segtree{
int maxi[4*MAXN],res[4*MAXN],len[4*MAXN];
ull hsh[MAXN];
pair<int,ull> calc(int k,int l,ull h,int v){
if(len[k]==1){
if(maxi[k]<v) return make_pair(l,h);
else{
ull res=h*BASE+maxi[k];
return make_pair(l+1,res);
}
}
if(maxi[k*2+1]>=v){
auto p=calc(k*2+1,l,h,v);
p.S=(p.S*pw[res[k]]+hsh[k]);
p.F+=res[k];
return p;
}
else return calc(k*2,l,h,v);
}
void pushup(int k){
maxi[k]=max(maxi[k*2],maxi[k*2+1]);
auto p=calc(k*2,0,0,maxi[k*2+1]);
hsh[k]=p.S; res[k]=p.F;
}
void build(int k,int l,int r,int id){
len[k]=r-l+1;
if(l==r){
maxi[k]=a[id][l];
res[k]=hsh[k]=0;
return;
}
int mid=(l+r)/2;
build(k*2,l,mid,id); build(k*2+1,mid+1,r,id);
pushup(k);
}
void update(int k,int l,int r,int pos,int v){
if(l==r){
maxi[k]=v;
res[k]=hsh[k]=0;
return;
}
int mid=(l+r)/2;
if(pos<=mid) update(k*2,l,mid,pos,v); else update(k*2+1,mid+1,r,pos,v);
pushup(k);
return;
}
}seg[2];
int main(){
pw[0]=1;
for(int i=1;i<=100000;i++) pw[i]=pw[i-1]*BASE;
for(int i=0;i<2;i++){
scanf("%d",&n[i]);
for(int j=1;j<=n[i];j++) scanf("%d",&a[i][j]);
seg[i].build(1,1,n[i],i);
}
scanf("%d",&m);
for(int i=0;i<m;i++){
int o,x,y;
scanf("%d%d%d",&o,&x,&y);
o--;
seg[o].update(1,1,n[o],x,y);
auto p=seg[0].calc(1,0,0,0);
auto q=seg[1].calc(1,0,0,0);
// printf("p=%d %llu q=%d %llu\n",p.F,p.S,q.F,q.S);
if(p==q) puts("YES"); else puts("NO");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 16168kb
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: 27ms
memory: 14900kb
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: 25ms
memory: 14524kb
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: 0
Accepted
time: 30ms
memory: 14944kb
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 YES YES YES YES NO 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 NO NO NO NO NO NO NO NO NO NO NO NO NO NO N...
result:
ok 200000 tokens
Test #5:
score: 0
Accepted
time: 24ms
memory: 14908kb
input:
4 1 1 2 2 1 1 200000 2 1 2 1 1 3 1 2 1 2 1 2 2 1 2 2 1 3 2 1 1 2 1 1 1 4 2 2 1 3 1 3 1 1 2 1 1 3 2 2 1 1 1 4 2 2 1 1 2 1 2 1 1 1 2 1 2 2 1 1 1 4 1 1 2 2 2 1 1 1 1 1 1 4 3 2 1 3 1 1 3 2 1 2 1 2 1 2 1 1 2 1 1 2 1 1 2 1 3 2 1 2 1 2 3 2 1 3 1 3 3 2 1 1 1 2 3 2 1 2 1 1 2 2 1 2 2 1 3 1 2 1 1 4 3 2 1 2 2 1...
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 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 YES NO NO NO NO YES NO NO NO NO YES YES NO NO NO NO NO NO NO NO NO N...
result:
ok 200000 tokens
Test #6:
score: 0
Accepted
time: 31ms
memory: 14704kb
input:
2 4 2 4 2 3 3 2 200000 1 1 2 1 2 2 1 2 2 1 2 4 1 1 2 1 2 4 2 2 1 1 1 3 2 3 2 2 3 1 2 2 4 2 3 2 2 2 1 1 1 4 1 2 4 2 2 1 1 1 2 2 1 2 2 4 4 1 2 4 1 2 3 2 4 4 2 3 1 2 1 3 2 3 1 2 2 1 1 1 2 2 2 1 1 2 3 1 2 2 1 2 1 1 2 4 1 2 4 1 1 3 1 1 4 2 1 3 1 1 1 1 2 4 2 1 2 2 3 4 1 2 4 2 2 1 1 2 1 2 3 2 1 2 3 2 3 3 1...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES NO NO NO NO NO NO NO NO NO NO NO YES YES YES 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 NO NO NO NO NO NO N...
result:
ok 200000 tokens
Test #7:
score: 0
Accepted
time: 35ms
memory: 14820kb
input:
7 3 3 4 1 1 3 3 5 3 3 2 1 4 200000 2 2 1 2 2 1 2 5 1 1 6 1 1 5 2 2 1 4 1 4 2 1 6 4 1 7 1 1 2 3 2 5 1 2 5 4 1 6 2 1 5 2 1 4 1 1 2 1 2 2 2 1 3 4 1 7 2 1 6 3 2 5 1 1 5 1 1 7 3 2 1 3 2 3 1 1 3 2 2 2 2 1 7 4 2 1 4 1 3 2 1 1 2 1 5 3 1 5 3 2 2 2 1 5 3 2 5 3 2 3 2 1 1 3 1 2 2 2 2 1 2 1 4 2 1 2 1 3 4 2 1 1 1...
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 YES NO NO NO NO NO NO NO NO NO NO NO NO NO...
result:
ok 200000 tokens
Test #8:
score: 0
Accepted
time: 27ms
memory: 14844kb
input:
1 3 7 4 4 5 5 5 5 4 200000 2 2 4 2 6 4 1 1 4 2 6 4 2 1 3 2 2 3 2 1 3 1 1 5 1 1 5 2 3 5 1 1 4 1 1 4 2 6 5 2 5 1 2 1 2 2 7 2 1 1 5 2 4 5 1 1 2 1 1 3 2 4 2 2 1 3 1 1 3 2 1 1 1 1 1 2 3 1 1 1 4 1 1 5 1 1 1 2 5 2 2 7 3 1 1 5 2 6 4 1 1 4 2 7 4 2 3 3 2 3 1 1 1 3 1 1 3 2 4 4 1 1 4 1 1 2 1 1 1 2 3 1 2 1 1 1 1...
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 #9:
score: 0
Accepted
time: 30ms
memory: 14852kb
input:
8 3 1 2 2 1 4 4 4 3 1 4 4 200000 1 2 1 1 5 1 2 1 1 2 1 1 2 2 2 2 3 1 1 5 5 1 6 2 1 2 5 1 3 1 1 5 1 2 1 5 2 1 2 1 4 4 2 3 3 1 4 3 2 2 2 2 3 1 1 6 4 1 1 3 1 2 3 2 2 5 2 3 3 2 1 3 2 3 4 2 1 4 2 2 5 2 2 4 2 2 2 1 3 1 1 8 2 2 2 3 1 2 2 1 1 2 1 1 1 1 3 1 2 1 3 2 2 3 1 6 2 2 2 4 1 6 3 2 1 1 1 1 4 2 1 4 2 1...
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 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 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 #10:
score: 0
Accepted
time: 30ms
memory: 14808kb
input:
3 6 1 5 2 5 3 200000 1 2 4 1 1 3 1 2 5 2 2 5 1 3 3 1 1 6 1 3 1 1 2 1 2 1 6 2 1 4 2 1 2 2 2 3 1 3 1 1 3 5 1 2 4 2 2 5 1 2 5 1 3 1 2 1 3 1 2 6 1 2 4 2 1 3 1 2 4 1 2 1 1 3 2 2 2 6 2 1 4 2 2 4 1 1 2 1 1 4 2 2 2 2 1 4 1 2 2 1 1 3 2 1 4 1 3 3 2 1 6 2 2 2 1 1 6 1 3 6 1 2 2 1 3 1 2 2 3 1 2 2 2 1 2 2 2 5 2 2...
output:
NO NO NO 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 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 YES NO NO NO NO NO NO YES YES NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO...
result:
ok 200000 tokens
Test #11:
score: 0
Accepted
time: 28ms
memory: 16112kb
input:
3 1 1 6 5 2 3 4 4 6 200000 2 3 5 2 5 5 1 1 4 1 2 4 1 1 1 2 4 3 2 1 2 1 1 6 2 2 2 2 5 4 1 3 4 1 3 4 2 3 5 2 1 6 1 1 1 2 3 4 2 3 5 2 2 5 1 1 5 1 2 2 1 3 2 2 2 1 1 3 5 2 3 6 1 3 3 2 1 3 2 5 3 1 1 1 2 4 4 2 5 1 2 2 5 1 2 2 1 2 3 2 4 5 1 3 5 2 1 1 2 5 1 1 2 1 2 5 4 2 3 1 2 1 6 1 1 2 1 3 6 1 2 1 2 3 6 1 1...
output:
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 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...
result:
ok 200000 tokens
Test #12:
score: 0
Accepted
time: 38ms
memory: 14764kb
input:
8 73198 31688 65092 21397 35031 58089 52944 16010 5 31090 97692 26708 44940 89767 200000 2 5 31191 1 1 60759 1 6 70508 1 2 97983 2 3 53563 1 4 22102 1 7 36211 1 3 33339 1 8 49224 1 7 82146 2 5 97668 1 4 13552 1 2 26414 2 4 3381 1 4 42198 1 4 28786 2 2 29892 2 2 77347 1 5 53766 2 5 55142 2 5 74266 1 ...
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 #13:
score: -100
Memory Limit Exceeded
input:
100000 45952 97807 4941 35929 10776 28013 47912 21386 48030 55110 1347 96260 91732 78252 37717 2556 44017 67045 91588 59689 86623 88384 41158 38652 77627 83554 48557 85544 94827 54704 86949 61451 79790 92480 74798 43911 65450 20096 17129 95952 87522 98877 41827 51143 42419 98384 27210 34607 91233 46...