QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #331460 | #7047. Pot!! | nickoless | WA | 4ms | 17592kb | C++14 | 2.8kb | 2024-02-18 10:31:29 | 2024-02-18 10:31:29 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=1e5+5;
int n,Q;
struct segement_tree{
#define ls p<<1
#define rs p<<1|1
int n;
struct info{
int l2,l3,l5,l7;
info(int x=0){
l2=l3=l5=l7=0;
switch(x){
case 0:break;
case 2:l2=1;break;
case 3:l3=1;break;
case 4:l2=2;break;
case 5:l5=1;break;
case 6:l2=1;l3=1;break;
case 7:l7=1;break;
case 8:l2=3;break;
case 9:l3=2;break;
}
}
info operator+(info x){
info t;
t.l2=l2+x.l2;
t.l3=l3+x.l3;
t.l5=l5+x.l5;
t.l7=l7+x.l7;
return t;
}
};
struct Node{
int mx;
int n2,n3,n5,n7;
info lazy;
Node(){};
}t[maxn<<2];
void f(int p,info x){
t[p].n2+=x.l2;
t[p].n3+=x.l3;
t[p].n5+=x.l5;
t[p].n7+=x.l7;
t[p].lazy=t[p].lazy+x;
t[p].mx=max(max(t[p].n2,t[p].n3),max(t[p].n5,t[p].n7));
}
void push_down(int p){
f(ls,t[p].lazy);
f(rs,t[p].lazy);
t[p].lazy=info();
}
Node merge_Node(Node a,Node b){
Node c;
c.n2=max(a.n2,b.n2);
c.n3=max(a.n3,b.n3);
c.n5=max(a.n5,b.n5);
c.n7=max(a.n7,b.n7);
c.mx=max(max(c.n2,c.n3),max(c.n5,c.n7));
return c;
}
void build(int p,int l,int r){
if(l==r)return;
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
t[p]=merge_Node(t[ls],t[rs]);
}
void build(int _n){
n=_n;
build(1,1,n);
}
void add(int p,int l,int r,int L,int R,info x){
if(L<=l && r<=R){
f(p,x);
return;
}
push_down(p);
int mid=(l+r)>>1;
if(L<=mid)add(ls,l,mid,L,R,x);
if(R>mid)add(rs,mid+1,r,L,R,x);
t[p]=merge_Node(t[ls],t[rs]);
}
void mul(int L,int R,int x){
add(1,1,n,L,R,info(x));
}
Node query(int p,int l,int r,int L,int R){
if(L<=l && r<=R){
return t[p];
}
push_down(p);
int mid=(l+r)>>1;
if(R<=mid)return query(ls,l,mid,L,R);
if(L>mid)return query(rs,mid+1,r,L,R);
return merge_Node(query(ls,l,mid,L,R),query(rs,mid+1,r,L,R));
}
int query(int L,int R){
Node t=query(1,1,n,L,R);
return t.mx;
}
void print(int p,int l,int r){
printf("[%d,%d] %d\n",l,r,t[p].mx);
printf("%d %d %d %d\n",t[p].n2,t[p].n3,t[p].n5,t[p].n7);
printf("%d %d %d %d\n",t[p].lazy.l2,t[p].lazy.l3,t[p].lazy.l5,t[p].lazy.l7);
if(l==r)return;
int mid=(l+r)>>1;
print(ls,l,mid);
print(rs,mid+1,r);
}
void print(){
print(1,1,n);
}
#undef ls
#undef rs
}tr;
int main(){
cin>>n>>Q;
tr.build(n);
// tr.print();
for(int i=1;i<=Q;i++){
string op;
cin>>op;
if(op=="MULTIPLY"){
int l,r,x;
cin>>l>>r>>x;
tr.mul(l,r,x);
}
else {
int l,r;
cin>>l>>r;
cout<<"ANSWER "<<tr.query(l,r)<<endl;
}
// tr.print();
}
return 0;
}
/*
5 6
MULTIPLY 3 5 2
MULTIPLY 2 5 3
MAX 1 5
MULTIPLY 1 4 2
MULTIPLY 2 5 5
MAX 3 5
*/
详细
Test #1:
score: 100
Accepted
time: 4ms
memory: 17580kb
input:
5 6 MULTIPLY 3 5 2 MULTIPLY 2 5 3 MAX 1 5 MULTIPLY 1 4 2 MULTIPLY 2 5 5 MAX 3 5
output:
ANSWER 1 ANSWER 2
result:
ok 2 lines
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 17592kb
input:
100 1000 MULTIPLY 3 13 8 MULTIPLY 35 86 9 MAX 5 92 MAX 30 86 MAX 4 99 MAX 36 66 MULTIPLY 27 41 5 MAX 21 40 MULTIPLY 5 20 10 MAX 7 98 MAX 10 10 MAX 40 44 MAX 27 47 MAX 37 54 MAX 61 72 MULTIPLY 10 13 8 MAX 19 30 MAX 27 96 MULTIPLY 54 94 9 MAX 29 88 MAX 7 45 MULTIPLY 21 96 7 MULTIPLY 77 98 9 MULTIPLY 3...
output:
ANSWER 3 ANSWER 2 ANSWER 3 ANSWER 2 ANSWER 2 ANSWER 3 ANSWER 3 ANSWER 2 ANSWER 2 ANSWER 2 ANSWER 2 ANSWER 1 ANSWER 2 ANSWER 4 ANSWER 6 ANSWER 3 ANSWER 6 ANSWER 6 ANSWER 6 ANSWER 1 ANSWER 4 ANSWER 2 ANSWER 6 ANSWER 3 ANSWER 6 ANSWER 8 ANSWER 8 ANSWER 8 ANSWER 7 ANSWER 7 ANSWER 7 ANSWER 7 ANSWER 8 ANS...
result:
wrong answer 6th lines differ - expected: 'ANSWER 4', found: 'ANSWER 3'