Submission #994736


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;
    long long val, lazyVal;
    int sum, lazySum, i;
    int sz;
    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, long long 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->sz=1;
    if(l)
        n->sz+=l->sz;
    if(r)
        n->sz+=r->sz;
    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, long long 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, int p)
{
    if(!n)
        return;
    down(n);
    traverse(n->left, p);
    int sz=0;
    if(n->left)
        sz+=n->left->sz;
    ans[n->sum+p+sz]=n->val;
    traverse(n->right, p+sz+1);
}

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

void getlistr(node *root, vector<int>& V, int& K, int p)
{
    if(!root || K==0)
        return;
    down(root);
    getlistr(root->right, V, K, p);
    if(K==0)
        return;
    int sz=0;
    if(root->left)
        sz+=root->left->sz;
    V.push_back(root->sum+p+sz);
    K--;
    getlistr(root->left, V, K, p+sz+1);
}

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-getRight(root)->val, 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, 0);
                kk=v.size()+1;
                getlist(tr, w, kk, 0);
                int n=v.size();
                for(int j=0; j<n; j++)
                    fa[v[j]]=w[n-j];
                root=tr;
                apply(root, -x, n, false);
            }
            else
            {
                tie(tl, tr)=split(root, x+1);
                int kk=MAX;
                vector<int> v, w;
                getlist(tr, v, kk, 0);
                kk=v.size()+1;
                getlistr(tl, w, kk, 0);
                int n=v.size();
                for(int j=0; j<n; j++)
                    fa[v[j]]=w[j+1];
                root=tl;
                apply(root, 0, 0, true);
            }
        }
    }
    traverse(root, 0);
    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 solve2()
{
    int x=0;
    for(int i=N; i>=3; i--)
        x=abs(x-A[i]);
    return A[1]-A[2]+x;
}

#include <random>
std::default_random_engine random_engine(0xdeadbeef);
template<class T>
inline T randint(T L, T R) { return std::uniform_int_distribution<T>(L, R)(random_engine); }

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

Submission Time
Task H - Tokaido
User FatalEagle
Language C++14 (GCC 5.4.1)
Score 0
Code Size 5703 Byte
Status MLE
Exec Time 1101 ms
Memory 348492 KB

Compile Error

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

Judge Result

Set Name sample dataset1 dataset2
Score / Max Score 0 / 0 0 / 700 0 / 900
Status
MLE × 2
AC × 5
MLE × 15
AC × 8
MLE × 29
Set Name Test Cases
sample sample-01.txt, sample-02.txt
dataset1 sample-01.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt
dataset2 sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, 02-15.txt, 02-16.txt
Case Name Status Exec Time Memory
01-01.txt MLE 1097 ms 345216 KB
01-02.txt AC 449 ms 86144 KB
01-03.txt MLE 881 ms 344448 KB
01-04.txt MLE 999 ms 344832 KB
01-05.txt MLE 1098 ms 345216 KB
01-06.txt MLE 1096 ms 345216 KB
01-07.txt MLE 957 ms 344576 KB
01-08.txt MLE 1083 ms 345216 KB
01-09.txt MLE 1081 ms 345216 KB
01-10.txt MLE 895 ms 348460 KB
01-11.txt MLE 882 ms 348252 KB
01-12.txt MLE 974 ms 348220 KB
01-13.txt MLE 1002 ms 347860 KB
01-14.txt MLE 943 ms 348376 KB
01-15.txt MLE 923 ms 348492 KB
01-16.txt AC 481 ms 86912 KB
01-17.txt AC 484 ms 86912 KB
01-18.txt AC 484 ms 86912 KB
01-19.txt AC 484 ms 86912 KB
02-01.txt MLE 930 ms 344576 KB
02-02.txt MLE 1099 ms 345216 KB
02-03.txt MLE 1101 ms 345216 KB
02-04.txt MLE 1101 ms 345216 KB
02-05.txt MLE 885 ms 344448 KB
02-06.txt MLE 1080 ms 345216 KB
02-07.txt MLE 1081 ms 345216 KB
02-08.txt MLE 881 ms 348420 KB
02-09.txt MLE 891 ms 346292 KB
02-10.txt MLE 894 ms 348392 KB
02-11.txt MLE 987 ms 348204 KB
02-12.txt MLE 945 ms 348488 KB
02-13.txt MLE 962 ms 348480 KB
02-14.txt AC 532 ms 88320 KB
02-15.txt AC 528 ms 88576 KB
02-16.txt AC 525 ms 88448 KB
sample-01.txt MLE 861 ms 348288 KB
sample-02.txt MLE 861 ms 348288 KB