TLE on test#10 求助

P1253 扶苏的问题

Fredericm @ 2023-05-11 17:22:54

#include<iostream>
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define lson l,m,id<<1
#define rson m+1,r,id<<1|1
int rd(){
    int ret = 0,f = 1;
    char c = getchar();
    while(!isdigit(c)) {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(isdigit(c)) {
        ret = ret * 10 + c - 48;
        c = getchar();
    }
    return ret * f;
}
void write(long long x){
    if(x<0) {
        x = -x;
      putchar('-');
    }
    short sta[31],top = 0;
    do
    {
        sta[top++]=  x%10;
        x /= 10;
    }while(x);
    while(top) putchar(sta[--top]+'0');
    puts("");
}

const int N=1e6+5;
const ll none=1e12;
int n,q,a[N],op,l,r;

ll tre[N<<2],t2[N<<2],t1[N<<2];

inline void pushup(int id) {tre[id]=max(tre[id<<1],tre[id<<1|1]);}
inline void pushdown(int id)
{
    if (t1[id]!=none)
    {
        t1[id<<1]=t1[id<<1|1]=t1[id];
        tre[id<<1]=tre[id<<1|1]=t1[id];
        t2[id<<1]=t2[id<<1|1]=0;
        t1[id]=none;
    }
    if (t2[id])
    {
        tre[id<<1]+=t2[id];
        tre[id<<1|1]+=t2[id];
        t2[id<<1]+=t2[id];
        t2[id<<1|1]+=t2[id];
        t2[id]=0;
    }
}

void build(int l,int r,int id)
{
    t1[id]=none;
    if (l==r) {tre[id]=a[l];return;}
    int m=l+r>>1;
    build(lson);build(rson);
    pushup(id);
}

void update(int L,int R,int k,int l,int r,int id)
{
    if (L<=l&&r<=R)
    {
        tre[id]=k;
        t1[id]=k;
        t2[id]=0;
        return;
    }
    int m=l+r>>1;
    pushdown(id);
    L<=m?update(L,R,k,lson):void(0);
    R>m?update(L,R,k,rson):void(0);
    pushup(id);
}

void add(int L,int R,int k,int l,int r,int id)
{
    if (L<=l&&r<=R)
    {
        tre[id]+=k;
        t2[id]+=k;
        return;
    }
    int m=l+r>>1;
    pushdown(id);
    L<=m?add(L,R,k,lson):void(0);
    R>m?add(L,R,k,rson):void(0);
    pushup(id);
}

ll query(int L,int R,int l,int r,int id)
{
    if (L<=l&&r<=R) return tre[id];
    int m=l+r>>1;
    pushdown(id);
    ll ret=-none;
    L<=m?ret=query(L,R,lson):0;
    R>m?ret=max(ret,query(L,R,rson)):0;
    return ret;
}

int main()
{
    n=rd(),q=rd();
    for (register int i=1;i<=n;++i) a[i]=rd();
    build(1,n,1);
    while (q--)
    {
        op=rd(),l=rd(),r=rd();
        op==1?update(l,r,rd(),1,n,1):op==2?add(l,r,rd(),1,n,1):write(query(l,r,1,n,1));
    }
}

by Fredericm @ 2023-05-11 18:47:11

救命!!! 这玩意已经调一天了


by Fredericm @ 2023-05-11 19:26:32

问题已解决 #define max()要比普通的max()函数慢得多


by Fredericm @ 2023-05-11 19:28:39

在此感谢@spider_oyster 的帮助


|