Submission #1091679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091679		ASN49K	Safety (NOI18_safety)	C++14	100 / 100	291 ms	21076 KiB

safety

#include <bits/stdc++.h>
using namespace std;
using i64=long long;
#define UNUSED -1
#define all(x) x.begin(),x.end()
#define pb push_back
const int mod=1e9+7,inf=1e9+1;
const int N=2e5;
mt19937 rng(69);
struct node
{
    i64 key;
    int pri,cnt;
    i64 lazy;
    node* l,* r;

    node(int key)
    {
        this->key=key;
        pri=rng();
        cnt=1;
        lazy=0;
        l=r=nullptr;
    }
    void add(int x)
    {
        key+=x;
        lazy+=x;
    }
    void push_down()
    {
        if(l!=nullptr)l->add(lazy);
        if(r!=nullptr)r->add(lazy);
        lazy=0;
    }
};
int count(node* t)
{
    if(t==nullptr)
    {
        return 0;
    }
    return t->cnt;
}
void recalc(node* t)
{
    t->cnt=count(t->l)+count(t->r)+1;
}

void split(node* t,node*& l,node*& r,int cnt)
{
    if(t==nullptr)
    {
        l=r=nullptr;
        return;
    }
    t->push_down();
    if(count(t->l)+1<=cnt)
    {
        split(t->r,t->r,r,cnt-count(t->l)-1);
        l=t;
    }
    else
    {
        split(t->l,l,t->l,cnt);
        r=t;
    }
    recalc(t);
}

void split_key(node* t,node*& l,node*& r,int key)
{
    if(t==nullptr)
    {
        l=r=nullptr;
        return;
    }
    t->push_down();
    if(t->key<=key)
    {
        split_key(t->r,t->r,r,key);
        l=t;
    }
    else
    {
        split_key(t->l,l,t->l,key);
        r=t;
    }
    recalc(t);
}


void merge(node*& t,node* l,node* r)
{
    if(l==nullptr)
    {
        t=r;
        return;
    }
    if(r==nullptr)
    {
        t=l;
        return;
    }
    l->push_down();
    r->push_down();
    if(l->pri >= r->pri)
    {
        merge(l->r,l->r,r);
        t=l;
    }
    else
    {
        merge(r->l,l,r->l);
        t=r;
    }
    recalc(t);
}

int leftest(node*& t)
{
    if(t->l==nullptr)
    {
        return t->key;
    }
    t->push_down();
    return leftest(t->l);
}
int rightest(node*& t)
{
    if(t->r==nullptr)
    {
        return t->key;
    }
    t->push_down();
    return rightest(t->r);
}
void print(node* t)
{
    if(t==nullptr)
    {
        return;
    }
    t->push_down();
    print(t->l);
    cout<<t->key<<' ';
    print(t->r);
}
int n,h;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>h;
    node* root=nullptr;
    i64 rez=0;
    int last_l=0,last_r=0;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        if(i!=1)
        {
            rez+=max(last_l-x , 0);
            rez+=max(x-last_r , 0);
        }
        node *l,*r;
        split_key(root,l,r,x);

        merge(l,l,new node(x));
        merge(l,l,new node(x));
        merge(root,l,r);
        split(root,l,r,i);
        assert(l!=nullptr);
        assert(r!=nullptr);
        l->add(-h);
        r->add(h);
        last_l=rightest(l),last_r=leftest(r);
        merge(root,l,r);

    }
    cout<<rez;
}

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 5 / 5
• Subtask 5: 6 / 6
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 22 / 22
• Subtask 9: 29 / 29