luogu 3488 [POI2009]LYZ-Ice Skates 线段树 + 思维

水深无声 2021-11-17 16:16 148阅读 0赞

Code:

#include <bits/stdc++.h>
    #define setIO(s) freopen(s".in","r",stdin), freopen(s".out","w",stdout)     
    #define maxn 1000000   
    #define ll long long   
    #define lson (now<<1) 
    #define rson ((now<<1)|1)      
    using namespace std;      
    int n,m; 
    ll k,d;    
    ll sum[maxn<<2],lmx[maxn<<2],rmx[maxn<<2],mx[maxn<<2];   
    void pushup(int l,int r,int now) {
        int mid=(l+r)>>1,ls=lson,rs=(r>mid)?rson:0;    
        sum[now]=sum[ls]+sum[rs];   
        lmx[now]=max(lmx[ls],sum[ls]+lmx[rs]);              
        rmx[now]=max(rmx[rs],sum[rs]+rmx[ls]);              
        mx[now]=rmx[ls]+lmx[rs];             
        mx[now]=max(mx[now], max(mx[ls], mx[rs]));             
    }     
    void build(int l,int r,int now) {
        if(l==r) {
            sum[now]=-k;                     
            return ;  
        } 
        int mid=(l+r)>>1;    
        build(l,mid,lson); 
        if(r>mid) build(mid+1,r,rson);           
        pushup(l,r,now);               
    }         
    void update(int l,int r,int now,int x,ll v) {
        if(l==r) {
            sum[now]+=v;          
            lmx[now]=rmx[now]=mx[now]=max(0ll, sum[now]);     
            return;  
        } 
        int mid=(l+r)>>1;    
        if(x<=mid) update(l,mid,lson,x,v); 
        else update(mid+1,r,rson,x,v); 
        pushup(l,r,now);     
    }
    int main() {
        // setIO("input");    
        scanf("%d%d%lld%lld",&n,&m,&k,&d);       
        build(1,n,1);          
        for(int i=1;i<=m;++i) {
            int r; 
            ll x;           
            scanf("%d%lld",&r,&x);      
            update(1,n,1,r,x);        
            if(mx[1] > k*d) printf("NIE\n"); 
            else printf("TAK\n");        
        } 
        return 0;         
    }

转载于:https://www.cnblogs.com/guangheli/p/11231718.html