Submission #548257

#	Time	Username	Problem	Language	Result	Execution time	Memory
548257		Deepesson	Divide and conquer (IZhO14_divide)	C++17	100 / 100	112 ms	50680 KiB

divide

#include <bits/stdc++.h>
#define MAX 10000000
using ll = long long;
struct node {
    int left,right;
    ll val;
};
const ll inf = (1LL<<60LL);
node mem[MAX*4];
int cur=1;
int alocar(void){
    int x = cur++;
    mem[x].val=inf;
    return x;
}
int inicio = alocar();
ll query(ll l,ll r,ll la=-inf,ll ra=inf,ll pos=inicio){
    if(!pos)return inf;
    if(l>ra||r<la)return inf;
  ///  std::cout<<"Explora "<<la<<" "<<ra<<" "<<l<<" "<<r<<"\n";
    if(la>=l&&ra<=r){
        return mem[pos].val;
    }
    ll m = (la+(4LL*inf)+ra)/2LL;
    m-=2LL*inf;
    return std::min(query(l,r,la,m,mem[pos].left),query(l,r,m+1,ra,mem[pos].right));
}
void update(ll t,ll k,ll la=-inf,ll ra=inf,ll pos=inicio){
    ll m = (la+(4LL*inf)+ra)/2LL;
    m-=2LL*inf;
    mem[pos].val=std::min(mem[pos].val,k);
   /// std::cout<<"Alterando "<<la<<" "<<ra<<" "<<" "<<m<<" "<<mem[pos].val<<"\n";
    if(la==ra)return;
    if(t>m){
        if(!mem[pos].right)mem[pos].right=alocar();
        update(t,k,m+1,ra,mem[pos].right);
    }else {
        if(!mem[pos].left)mem[pos].left=alocar();
        update(t,k,la,m,mem[pos].left);
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int N;
    std::cin>>N;
    ll resp=0;
    ll prefouro=0;
    ll prefener=0;
    for(int i=0;i!=N;++i){
        ll pos,gold,energy;
        std::cin>>pos>>gold>>energy;
        update(pos-prefener,prefouro);
      ///  std::cout<<"Upd "<<pos-1-prefener<<" "<<prefouro<<"\n";
        prefener+=energy;
        ll valor = -pos+prefener;
        ll la = -valor,ra=inf;
        ll ponto = query(std::min(la,ra),std::max(la,ra));
        prefouro+=gold;
       /// std::cout<<la<<" "<<ra<<" "<<valor<<" "<<prefouro<<" "<<ponto<<"\n";
        resp=std::max(resp,prefouro-ponto);
    }
    std::cout<<resp<<"\n";
}

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