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 |
|
|
|
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 |