제출 #140528

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
140528		rzbt	금 캐기 (IZhO14_divide)	C++14	100 / 100	129 ms	10528 KiB

divide

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define MAXN 100005
typedef long long ll;

using namespace std;

pair<ll,pair<ll,ll> >  niz[MAXN];

ll n;
ll prefix[MAXN];
ll seg[4*MAXN];
ll lazy[4*MAXN];




void izgradi(ll l,ll d,ll k){
    seg[k]=-1e9-7;
    if(l==d)
        return;

    ll mid=(l+d)/2;
    izgradi(l,mid,k+k);
    izgradi(mid+1,d,k+k+1);
}

void dodaj(ll l,ll d,ll tl,ll td,ll x,ll k){
    if(lazy[k]){
        seg[k]+=lazy[k];
        if(l!=d){
            lazy[k+k]+=lazy[k];
            lazy[k+k+1]+=lazy[k];
        }
        lazy[k]=0;
    }
    if(l>td || d<tl)return;
    if(l>=tl && d<=td){
        lazy[k]=x;
        seg[k]+=lazy[k];
        if(l!=d){
            lazy[k+k]+=lazy[k];
            lazy[k+k+1]+=lazy[k];
        }
        lazy[k]=0;
        return;
    }
    ll mid=(l+d)/2;
    dodaj(l,mid,tl,td,x,k+k);
    dodaj(mid+1,d,tl,td,x,k+k+1);

    seg[k]=max(seg[k+k],seg[k+k+1]);
}

void odsljakaj(ll l,ll d,ll k){
    if(lazy[k]){
        seg[k]+=lazy[k];
        if(l!=d){
            lazy[k+k]+=lazy[k];
            lazy[k+k+1]+=lazy[k];
        }
        lazy[k]=0;
    }
}


ll setnja(ll l,ll d,ll k){
    if(seg[k]<0)return -1;
    if(l==d)return l;

    ll mid=(l+d)/2;
    odsljakaj(l,mid,k+k);
    odsljakaj(mid+1,d,k+k+1);

    if(seg[k+k]>=0)return setnja(l,mid,k+k);
    else return setnja(mid+1,d,k+k+1);


}

ll res;


int main()
{
    scanf("%lld", &n);
    for(ll i=1;i<=n;i++){
        ll x,g,e;
        scanf("%lld %lld %lld", &x, &g, &e);
        niz[i]=mp(x,mp(g,e));
    }
    izgradi(1,n,1);
    prefix[1]=niz[1].second.first;
    res=prefix[1];
    dodaj(1,n,1,1,niz[1].S.S,1);
    dodaj(1,n,1,1,1e9+7,1);
    for(ll i=2;i<=n;i++){
        prefix[i]=prefix[i-1]+niz[i].S.F;
        dodaj(1,n,i,i,1e9+7,1);
        dodaj(1,n,1,i,niz[i].S.S,1);
        dodaj(1,n,1,i-1,niz[i-1].F-niz[i].F,1);
        ll gde=setnja(1,n,1);
        if(gde==-1){
            printf("SDAFGFAFAFSSAF");
            return 0;
        }
        res=max(res,prefix[i]-prefix[gde-1]);

    }
    printf("%lld",res);
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

divide.cpp: In function 'int main()':
divide.cpp:90:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &n);
     ~~~~~^~~~~~~~~~~~
divide.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld %lld", &x, &g, &e);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52