Submission #994149
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]>=MAX)
return A[1]-A[2]+A[N]-S;
return A[1]-A[2]+ans[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
Submission Time |
|
Task |
H - Tokaido |
User |
FatalEagle |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
4827 Byte |
Status |
WA |
Exec Time |
704 ms |
Memory |
75392 KB |
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
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 |
AC |
628 ms |
73472 KB |
01-02.txt |
AC |
394 ms |
70528 KB |
01-03.txt |
AC |
419 ms |
70656 KB |
01-04.txt |
AC |
536 ms |
72192 KB |
01-05.txt |
AC |
633 ms |
73472 KB |
01-06.txt |
AC |
633 ms |
73472 KB |
01-07.txt |
AC |
498 ms |
71296 KB |
01-08.txt |
AC |
615 ms |
72960 KB |
01-09.txt |
AC |
617 ms |
73088 KB |
01-10.txt |
WA |
417 ms |
72880 KB |
01-11.txt |
WA |
414 ms |
70872 KB |
01-12.txt |
WA |
514 ms |
72104 KB |
01-13.txt |
WA |
531 ms |
72316 KB |
01-14.txt |
WA |
488 ms |
71900 KB |
01-15.txt |
WA |
468 ms |
71760 KB |
01-16.txt |
WA |
428 ms |
71296 KB |
01-17.txt |
AC |
429 ms |
71296 KB |
01-18.txt |
AC |
430 ms |
71296 KB |
01-19.txt |
AC |
428 ms |
71296 KB |
02-01.txt |
AC |
475 ms |
71424 KB |
02-02.txt |
AC |
672 ms |
75392 KB |
02-03.txt |
AC |
704 ms |
74112 KB |
02-04.txt |
AC |
665 ms |
73856 KB |
02-05.txt |
AC |
455 ms |
71424 KB |
02-06.txt |
WA |
651 ms |
73600 KB |
02-07.txt |
WA |
655 ms |
73856 KB |
02-08.txt |
WA |
450 ms |
73480 KB |
02-09.txt |
WA |
460 ms |
72356 KB |
02-10.txt |
WA |
477 ms |
72684 KB |
02-11.txt |
WA |
563 ms |
73632 KB |
02-12.txt |
WA |
543 ms |
73548 KB |
02-13.txt |
WA |
553 ms |
73668 KB |
02-14.txt |
WA |
474 ms |
72832 KB |
02-15.txt |
AC |
474 ms |
72960 KB |
02-16.txt |
AC |
473 ms |
72832 KB |
sample-01.txt |
AC |
395 ms |
70528 KB |
sample-02.txt |
AC |
395 ms |
70528 KB |