Submission #994209

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

const int MAX=1000000;
int N, M, S;
int A[200001];
int ans[1000001];
int fa[1000001];

struct node
{
    node *left, *right;
    unsigned int pri;
    int val, lazyVal;
    int sum, lazySum, i;
    bool rev;
};

unsigned int genPri()
{
    unsigned int x=rand();
    unsigned int y=rand();
    return (x<<16)|y;
}

node* reassign(node *n, node *l, node *r, unsigned int pri, int val, int sum, int i, bool rev)
{
    n->left=l;
    n->right=r;
    n->pri=pri;
    n->val=val;
    n->lazyVal=0;
    n->sum=sum;
    n->lazySum=0;
    n->i=i;
    n->rev=rev;
    return n;
}

node* reassign(node *n, node *l, node *r)
{
    return reassign(n, l, r, n->pri, n->val, n->sum, n->i, n->rev);
}

void apply(node *n, int lazyVal, int lazySum, bool rev)
{
    n->val+=lazyVal;
    n->lazyVal+=lazyVal;
    n->sum+=lazySum;
    n->lazySum+=lazySum;
    if(rev)
    {
        n->rev^=1;
        swap(n->left, n->right);
    }
}

void down(node *n)
{
    if(n->left)
        apply(n->left, n->lazyVal, n->lazySum, n->rev);
    if(n->right)
        apply(n->right, n->lazyVal, n->lazySum, n->rev);
    n->lazyVal=0;
    n->lazySum=0;
    n->rev=false;
}

node* getLeft(node *n)
{
    while(n->left)
    {
        down(n);
        n=n->left;
    }
    return n;
}

node* getRight(node *n)
{
    while(n->right)
    {
        down(n);
        n=n->right;
    }
    return n;
}

// {<, >=}
pair<node*, node*> split(node *n, int k)
{
    if(!n)
        return {nullptr, nullptr};
    down(n);
    node *l, *r;
    if(n->val<k)
    {
        tie(l, r)=split(n->right, k);
        reassign(n, n->left, l);
        return {n, r};
    }
    tie(l, r)=split(n->left, k);
    reassign(n, r, n->right);
    return {l, n};
}

// all l <= r
node* merge(node *l, node *r)
{
    if(!l)
        return r;
    if(!r)
        return l;
    down(l);
    down(r);
    if(l->pri<r->pri)
        return reassign(l, l->left, merge(l->right, r));
    return reassign(r, merge(l, r->left), r->right);
}

node* ins(node *root, node *n)
{
    node *l, *r;
    tie(l, r)=split(root, n->val);
    return merge(l, merge(n, r));
}

void traverse(node *n)
{
    if(!n)
        return;
    down(n);
    ans[n->i]=n->val;
    traverse(n->left);
    traverse(n->right);
}

void getlist(node *root, vector<int>& V, int& K)
{
    if(!root || K==0)
        return;
    down(root);
    getlist(root->left, V, K);
    if(K==0)
        return;
    V.push_back(root->i);
    K--;
    getlist(root->right, V, K);
}

int find(int x)
{
    if(x!=fa[x])
        return fa[x]=find(fa[x]);
    return fa[x];
}

void prep()
{
    node *root=nullptr;
    for(int i=0; i<=MAX; i++)
    {
        fa[i]=i;
        node *n=reassign(new node(), nullptr, nullptr, genPri(), i, 0, i, false);
        if(!root)
            root=n;
        else
            root=ins(root, n);
    }
    for(int i=N-1; i>=3; i--)
    {
        int x=A[i];
        if(x<=getLeft(root)->val)
            apply(root, -x, 0, false);
        else if(x>=getRight(root)->val)
            apply(root, -x, 0, true);
        else
        {
            node *tl, *tr;
            if(abs(getLeft(root)->val-x)<=abs(x-getRight(root)->val))
            {
                tie(tl, tr)=split(root, x);
                int kk=MAX;
                vector<int> v, w;
                getlist(tl, v, kk);
                kk=v.size()+1;
                getlist(tr, w, kk);
                int n=v.size();
                for(int j=0; j<n; j++)
                    fa[v[j]]=w[n-j];
                root=tr;
                apply(root, -x, 0, false);
            }
            else
            {
                tie(tl, tr)=split(root, x);
                int kk=MAX;
                vector<int> v, w;
                getlist(tr, v, kk);
                kk=v.size()+1;
                getlist(tl, w, kk);
                int n=v.size();
                for(int j=0; j<n; j++)
                    fa[v[j]]=w[n-j];
                root=tl;
                apply(root, -x, 0, true);
            }
        }
    }
    traverse(root);
    for(int i=0; i<=MAX; i++)
        ans[i]=ans[find(fa[i])];
    for(int i=3; i<=N-1; i++)
        S+=A[i];
}

int solve()
{
    if(A[N]>=S)
        return A[1]-A[2]+A[N]-S;
    return A[1]-A[2]+ans[find(A[N])];
    int x=0;
    for(int i=N; i>=3; i--)
        x=abs(x-A[i]);
    return A[1]-A[2]+x;
}

int main()
{
    scanf("%d", &N);
    for(int i=1; i<N; i++)
        scanf("%d", A+i);
    prep();
    scanf("%d", &M);
    while(M--)
    {
        scanf("%d", A+N);
        printf("%d\n", solve());
    }
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:231:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
                    ^
./Main.cpp:233:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", A+i);
                         ^
./Main.cpp:235:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &M);
                    ^
./Main.cpp:238:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", A+N);
                         ^

Judge Result