QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#521808#7047. Pot!!blhxzjr#AC ✓134ms40328kbC++203.1kb2024-08-16 15:12:292024-08-16 15:12:29

Judging History

你现在查看的是最新测评结果

  • [2024-08-16 15:12:29]
  • 评测
  • 测评结果:AC
  • 用时:134ms
  • 内存:40328kb
  • [2024-08-16 15:12:29]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define pb push_back
#define endl '\n'
#define int long long 
using ll=long long;
const int N=2e5+10;
#define inf 1e9

int n,m,k,_;


#define ls id<<1
#define rs id<<1|1
struct seg{
    int sum[5];
    int lazy[5];
    int len;
    int tol;
    int mx[5];
}t[N<<2];
#define len(x) t[x].len
#define tol(x) t[x].tol
inline void up(int id){
    rep(i,1,4){
        t[id].mx[i]=max(t[ls].mx[i],t[rs].mx[i]);
        t[id].sum[i]=t[ls].sum[i]+ t[rs].sum[i];
        tol(id)=max(tol(id),t[id].mx[i]);
    }
    len(id)=len(ls)+len(rs);
}
void build(int id,int l,int r){
    if(l==r){
        rep(i,1,4){
            t[id].mx[i]=0;
            t[id].sum[i]=t[id].lazy[i]=0;
            tol(id)=0;
        }
        len(id)=1; return;
    }
    int mid=l+r>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    up(id);
}
void settag(int id,int tt,int x){
    t[id].sum[tt]+=len(id)*x;
    t[id].mx[tt]+=x;
    tol(id)=max(tol(id),t[id].mx[tt]);
    t[id].lazy[tt]+=x;
}
void down(int id){
    rep(i,1,4){
        if(!t[id].lazy[i]) continue;
        settag(ls,i,t[id].lazy[i]);
        settag(rs,i,t[id].lazy[i]);
        t[id].lazy[i]=0;
    }
}
void modify(int id,int l,int r,int ql,int qr,int tt,int x){
    if(ql<=l&&r<=qr){
        settag(id,tt,x); return;
    }
    down(id);
    int mid=l+r>>1;
    if(qr<=mid) modify(ls,l,mid,ql,qr,tt,x);
    else if(ql>mid) modify(rs,mid+1,r,ql,qr,tt,x);
    else modify(ls,l,mid,ql,qr,tt,x),modify(rs,mid+1,r,ql,qr,tt,x);
    up(id);
}
int query(int id,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr){
        return tol(id);
    }
    down(id);
    int mid=l+r>>1;
    if(qr<=mid)  return query(ls,l,mid,ql,qr);
    else if(ql>mid) return query(rs,mid+1,r,ql,qr);
    else return max(query(ls,l,mid,ql,qr),query(rs,mid+1,r,ql,qr));
}
void solve(){
    int q;
    cin>>n>>q;
    build(1,1,n);
    rep(i,1,q){
        string op;
        int l,r,x;
        cin>>op>>l>>r;
        if(op=="MAX"){
            cout<<"ANSWER "<<query(1,1,n,l,r)<<endl;
        }
        else{
            cin>>x;
            if(x==2){
                modify(1,1,n,l,r,1,1);
            }
            else if(x==3){
                modify(1,1,n,l,r,2,1);
            }
            else if(x==4){
                modify(1,1,n,l,r,1,2);
            }
            else if(x==5){
                modify(1,1,n,l,r,3,1);
            }
            else if(x==6){
                modify(1,1,n,l,r,1,1);
                modify(1,1,n,l,r,2,1);
            }
            else if(x==7){
                modify(1,1,n,l,r,4,1);
            }
            else if(x==8){
                modify(1,1,n,l,r,1,3);
            }
            else if(x==9){
                modify(1,1,n,l,r,2,2);
            }
            else if(x==10){
                modify(1,1,n,l,r,1,1);
                modify(1,1,n,l,r,3,1);
            }
        }
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    _=1;
    while(_--){
        solve();
        if(_) cout<<endl;
    }
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3680kb

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: 0
Accepted
time: 1ms
memory: 3624kb

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 4
ANSWER 4
ANSWER 2
ANSWER 2
ANSWER 2
ANSWER 2
ANSWER 1
ANSWER 2
ANSWER 4
ANSWER 7
ANSWER 4
ANSWER 6
ANSWER 7
ANSWER 6
ANSWER 1
ANSWER 4
ANSWER 2
ANSWER 8
ANSWER 4
ANSWER 6
ANSWER 11
ANSWER 11
ANSWER 11
ANSWER 7
ANSWER 7
ANSWER 7
ANSWER 7
ANSWER 8
...

result:

ok 491 lines

Test #3:

score: 0
Accepted
time: 3ms
memory: 4160kb

input:

1000 10000
MULTIPLY 303 613 4
MAX 205 586
MULTIPLY 392 430 10
MAX 299 404
MAX 566 836
MAX 427 741
MAX 240 721
MAX 520 805
MULTIPLY 107 698 10
MULTIPLY 244 610 3
MAX 627 747
MULTIPLY 537 554 9
MULTIPLY 213 772 8
MAX 419 930
MAX 127 696
MAX 554 894
MAX 588 729
MAX 307 845
MAX 496 921
MULTIPLY 77 598 5...

output:

ANSWER 2
ANSWER 3
ANSWER 2
ANSWER 3
ANSWER 3
ANSWER 2
ANSWER 1
ANSWER 7
ANSWER 7
ANSWER 6
ANSWER 6
ANSWER 7
ANSWER 6
ANSWER 7
ANSWER 7
ANSWER 4
ANSWER 7
ANSWER 2
ANSWER 7
ANSWER 7
ANSWER 1
ANSWER 9
ANSWER 9
ANSWER 6
ANSWER 10
ANSWER 9
ANSWER 11
ANSWER 11
ANSWER 10
ANSWER 10
ANSWER 11
ANSWER 12
ANSWE...

result:

ok 4965 lines

Test #4:

score: 0
Accepted
time: 16ms
memory: 9544kb

input:

10000 10000
MULTIPLY 6735 9303 4
MAX 4205 5392
MAX 2299 3986
MAX 2836 4566
MULTIPLY 4427 8240 8
MULTIPLY 520 8805 9
MAX 3010 8107
MAX 4040 4244
MULTIPLY 2537 2627 9
MAX 1772 8461
MULTIPLY 930 4910 10
MULTIPLY 2696 4127 9
MAX 894 8588
MULTIPLY 4845 7307 6
MAX 2598 5921
MULTIPLY 446 6935 4
MAX 8903 90...

output:

ANSWER 0
ANSWER 0
ANSWER 0
ANSWER 5
ANSWER 2
ANSWER 5
ANSWER 5
ANSWER 5
ANSWER 2
ANSWER 8
ANSWER 8
ANSWER 3
ANSWER 8
ANSWER 7
ANSWER 3
ANSWER 10
ANSWER 5
ANSWER 9
ANSWER 11
ANSWER 11
ANSWER 9
ANSWER 14
ANSWER 11
ANSWER 9
ANSWER 15
ANSWER 3
ANSWER 0
ANSWER 12
ANSWER 15
ANSWER 15
ANSWER 11
ANSWER 16
A...

result:

ok 4979 lines

Test #5:

score: 0
Accepted
time: 90ms
memory: 9676kb

input:

10000 100000
MULTIPLY 6735 9303 7
MULTIPLY 5392 9430 10
MULTIPLY 2836 7404 7
MULTIPLY 4427 8240 5
MAX 4698 8805
MULTIPLY 3010 4610 10
MAX 747 2627
MULTIPLY 8461 8554 7
MULTIPLY 930 4910 7
MULTIPLY 2696 4554 7
MAX 4729 4845
MULTIPLY 496 5921 7
MULTIPLY 446 6935 3
MULTIPLY 5694 9059 10
MULTIPLY 2223 2...

output:

ANSWER 2
ANSWER 0
ANSWER 2
ANSWER 4
ANSWER 2
ANSWER 7
ANSWER 3
ANSWER 7
ANSWER 7
ANSWER 6
ANSWER 2
ANSWER 3
ANSWER 6
ANSWER 4
ANSWER 7
ANSWER 6
ANSWER 7
ANSWER 3
ANSWER 7
ANSWER 7
ANSWER 7
ANSWER 7
ANSWER 6
ANSWER 7
ANSWER 7
ANSWER 7
ANSWER 7
ANSWER 8
ANSWER 9
ANSWER 5
ANSWER 3
ANSWER 12
ANSWER 8
AN...

result:

ok 50025 lines

Test #6:

score: 0
Accepted
time: 134ms
memory: 38460kb

input:

100000 100000
MULTIPLY 7720 11613 9
MAX 46735 69303
MAX 4205 34586
MAX 19430 55392
MAX 33986 62299
MAX 32836 67404
MULTIPLY 30613 94566 5
MULTIPLY 1143 40741 4
MAX 38240 94427
MAX 60520 92721
MAX 64698 68805
MAX 18107 43010
MAX 54610 64244
MULTIPLY 20977 34040 6
MAX 747 52627
MULTIPLY 18458 72537 2
...

output:

ANSWER 0
ANSWER 2
ANSWER 0
ANSWER 0
ANSWER 0
ANSWER 2
ANSWER 1
ANSWER 1
ANSWER 2
ANSWER 1
ANSWER 3
ANSWER 3
ANSWER 2
ANSWER 5
ANSWER 5
ANSWER 5
ANSWER 5
ANSWER 3
ANSWER 13
ANSWER 8
ANSWER 9
ANSWER 13
ANSWER 13
ANSWER 10
ANSWER 15
ANSWER 17
ANSWER 17
ANSWER 6
ANSWER 14
ANSWER 19
ANSWER 12
ANSWER 21
A...

result:

ok 49954 lines

Test #7:

score: 0
Accepted
time: 119ms
memory: 38708kb

input:

100000 100000
MULTIPLY 46735 69303 4
MAX 4205 7720
MAX 19430 21239
MAX 2438 62299
MAX 8856 32836
MAX 11798 40741
MULTIPLY 38240 92721 6
MAX 32286 68805
MAX 10451 18107
MAX 30613 54610
MAX 5854 34040
MULTIPLY 52627 72537 4
MAX 1143 78461
MAX 282 97213
MAX 20538 50930
MULTIPLY 54127 62696 2
MAX 8946 3...

output:

ANSWER 0
ANSWER 0
ANSWER 2
ANSWER 0
ANSWER 0
ANSWER 3
ANSWER 0
ANSWER 3
ANSWER 0
ANSWER 5
ANSWER 5
ANSWER 3
ANSWER 0
ANSWER 0
ANSWER 1
ANSWER 6
ANSWER 7
ANSWER 6
ANSWER 7
ANSWER 7
ANSWER 7
ANSWER 8
ANSWER 3
ANSWER 9
ANSWER 8
ANSWER 12
ANSWER 12
ANSWER 12
ANSWER 11
ANSWER 7
ANSWER 6
ANSWER 9
ANSWER 1...

result:

ok 50061 lines

Test #8:

score: 0
Accepted
time: 123ms
memory: 40196kb

input:

100000 100000
MULTIPLY 39 69303 4
MAX 4205 7720
MAX 19430 21239
MAX 2438 62299
MAX 8856 32836
MAX 11798 40741
MULTIPLY 8366 38240 5
MAX 32286 68805
MAX 10451 18107
MAX 30613 54610
MAX 5854 34040
MULTIPLY 28101 52627 9
MAX 1143 78461
MAX 282 97213
MAX 20538 50930
MULTIPLY 15922 54127 3
MAX 8946 30894...

output:

ANSWER 2
ANSWER 2
ANSWER 2
ANSWER 2
ANSWER 2
ANSWER 2
ANSWER 2
ANSWER 2
ANSWER 2
ANSWER 2
ANSWER 2
ANSWER 2
ANSWER 3
ANSWER 2
ANSWER 7
ANSWER 7
ANSWER 15
ANSWER 15
ANSWER 15
ANSWER 15
ANSWER 15
ANSWER 17
ANSWER 15
ANSWER 18
ANSWER 18
ANSWER 22
ANSWER 22
ANSWER 21
ANSWER 25
ANSWER 25
ANSWER 25
ANSWER...

result:

ok 50061 lines

Test #9:

score: 0
Accepted
time: 107ms
memory: 38860kb

input:

100000 100000
MULTIPLY 39 7720 8
MULTIPLY 2438 21239 7
MULTIPLY 8856 11798 3
MAX 8366 33986
MULTIPLY 10451 32286 9
MAX 30613 94566
MULTIPLY 5854 28101 8
MAX 1143 92721
MAX 282 68805
MAX 18107 20538
MAX 15922 54610
MAX 8946 34040
MULTIPLY 2998 26286 7
MULTIPLY 14681 20977 5
MULTIPLY 21656 31892 7
MUL...

output:

ANSWER 1
ANSWER 2
ANSWER 6
ANSWER 6
ANSWER 3
ANSWER 3
ANSWER 3
ANSWER 6
ANSWER 6
ANSWER 6
ANSWER 6
ANSWER 6
ANSWER 3
ANSWER 6
ANSWER 9
ANSWER 10
ANSWER 10
ANSWER 10
ANSWER 10
ANSWER 10
ANSWER 7
ANSWER 13
ANSWER 16
ANSWER 10
ANSWER 16
ANSWER 13
ANSWER 16
ANSWER 17
ANSWER 17
ANSWER 17
ANSWER 15
ANSWER...

result:

ok 50085 lines

Test #10:

score: 0
Accepted
time: 129ms
memory: 38672kb

input:

100000 100000
MULTIPLY 39 69303 8
MULTIPLY 21239 34586 9
MULTIPLY 8856 55392 9
MAX 33986 62299
MAX 32836 94566
MULTIPLY 8366 94427 4
MAX 60520 92721
MULTIPLY 10451 64698 5
MULTIPLY 5854 43010 4
MAX 34040 64244
MULTIPLY 1143 52627 4
MULTIPLY 20538 38554 2
MULTIPLY 8946 31772 7
MULTIPLY 2998 44910 3
M...

output:

ANSWER 4
ANSWER 4
ANSWER 5
ANSWER 7
ANSWER 10
ANSWER 10
ANSWER 10
ANSWER 15
ANSWER 17
ANSWER 20
ANSWER 20
ANSWER 20
ANSWER 17
ANSWER 2
ANSWER 23
ANSWER 23
ANSWER 2
ANSWER 17
ANSWER 17
ANSWER 23
ANSWER 15
ANSWER 23
ANSWER 10
ANSWER 17
ANSWER 25
ANSWER 26
ANSWER 25
ANSWER 25
ANSWER 26
ANSWER 8
ANSWER ...

result:

ok 50027 lines

Test #11:

score: 0
Accepted
time: 104ms
memory: 40328kb

input:

100000 100000
MULTIPLY 7720 21239 9
MAX 8366 11798
MAX 10451 30613
MAX 1143 28101
MAX 15922 20538
MAX 2998 26286
MULTIPLY 20977 31892 3
MULTIPLY 1324 18458 2
MULTIPLY 9726 32279 9
MULTIPLY 841 18588 7
MAX 12618 23612
MULTIPLY 868 29534 4
MAX 17888 31598
MULTIPLY 12213 31112 2
MULTIPLY 7630 29405 5
M...

output:

ANSWER 2
ANSWER 2
ANSWER 2
ANSWER 2
ANSWER 2
ANSWER 5
ANSWER 5
ANSWER 5
ANSWER 3
ANSWER 5
ANSWER 5
ANSWER 6
ANSWER 11
ANSWER 11
ANSWER 9
ANSWER 11
ANSWER 9
ANSWER 12
ANSWER 6
ANSWER 12
ANSWER 12
ANSWER 12
ANSWER 12
ANSWER 5
ANSWER 12
ANSWER 12
ANSWER 12
ANSWER 12
ANSWER 15
ANSWER 15
ANSWER 15
ANSWER...

result:

ok 49817 lines