Submission #1034099
Source Code Expand
#include <bits/stdc++.h>
#define FOR(i,a,b) for( ll i = (a); i < (ll)(b); i++ )
#define REP(i,n) FOR(i,0,n)
#define YYS(x,arr) for(auto& x:arr)
#define ALL(x) (x).begin(),(x).end()
#define SORT(x) sort( (x).begin(),(x).end() )
#define REVERSE(x) reverse( (x).begin(),(x).end() )
#define UNIQUE(x) (x).erase( unique( ALL( (x) ) ) , (x).end() )
#define PW(x) (1LL<<(x))
#define SZ(x) ((ll)(x).size())
#define SHOW(x) cout << #x << " = " << x << endl
#define SHOWA(x,n) for( int i = 0; i < n; i++ ){ cout << x[i] << " "; } cout << endl
#define pb emplace_back
#define fi first
#define se second
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<ld> vd;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<vpl> gr;
typedef vector<vl> ml;
typedef vector<vd> md;
typedef vector<vi> mi;
const ll INF = (ll)1e9 + 10;
const ll INFLL = (ll)1e18 + 10;
const ld EPS = 1e-12;
const ll MOD = 1e9+7;
template<class T> T &chmin( T &a , const T &b ){ return a = min(a,b); }
template<class T> T &chmax( T &a , const T &b ){ return a = max(a,b); }
template<class T> inline T sq( T a ){ return a * a; }
ll in(){ ll x; scanf( "%lld" , &x ); return x; }
char yuyushiki[1000010]; string stin(){ scanf( "%s" , yuyushiki ); return yuyushiki; }
// head
struct ConvexHullTrick{
vi st;
vl a, b;
int s, t, it;
void init( int n ){
st = vi( n );
a.clear(); b.clear();
s = t = 0;
}
bool check( int i , int j , int k ){
return ( a[i] - a[k] ) * ( b[j] - b[i] ) <= ( a[i] - a[j] ) * ( b[k] - b[i] );
}
void add( ll ca , ll cb ){
a.pb( ca ); b.pb( cb );
while( s <= t-2 && check( st[t-2] , st[t-1] , SZ(a)-1 ) ) t--;
st[t++] = SZ(a)-1;
}
ll f( int i , ll x ){
return a[i] * x + b[i];
}
ll query( ll x ){
while( s <= t-2 && f(st[t-1],x) <= f(st[t-2],x) ) t--;
return f(st[t-1],x);
}
};
ConvexHullTrick cft;
vl t[2];
vl d[2];
vl sum[2];
vl yuyu( int q , int l , int r , int p = INF ){
int n = r-l;
vl dp( n+1 , 0 );
cft.init( n+1 );
cft.add( -l , d[q][l] + sum[q][l] + l * ( l - 1 ) / 2 );
dp[0] = d[q][l];
FOR( i , l , r ){
dp[i+1-l] = cft.query( i+1 ) + ( i + 1 ) * ( i + 2 ) / 2 - sum[q][i+1];
if( i+1 <= p ){
if( p == INF ){
chmax( dp[i+1-l] , dp[i-l] );
} else {
dp[i+1-l] = d[q][i+1];
}
cft.add( -(i+1) , dp[i+1-l] + sum[q][i+1] + i * ( i + 1 ) / 2 );
}
}
return dp;
}
int n, q;
ll u[300010], nu[300010];
void rec( int l , int r ){
if( l == r ){
return;
}
int m = ( l + r ) / 2;
vl f = yuyu( 0 , l , r , m );
vl dp( r-l , -INFLL );
for( int i = r-1; i >= m; i-- ){
dp[i-l] = f[i+1-l] + d[1][n-1-i];
if( i < r-1 ){
chmax( dp[i-l] , dp[i-l+1] );
}
chmax( u[i] , dp[i-l] );
}
vl b = yuyu( 1 , n-r , n-l , n-1-m );
dp = vl( r-l , -INFLL );
FOR( i , l , m+1 ){
dp[i-l] = d[0][i] + b[r-i];
if( i > l ){
chmax( dp[i-l] , dp[i-l-1] );
}
chmax( u[i] , dp[i-l] );
}
rec( l , m );
rec( m+1 , r );
}
int main(){
n = in();
REP( i , n ){
t[0].pb( in() );
}
t[1] = t[0];
REVERSE( t[1] );
d[0] = d[1] = sum[0] = sum[1] = vl( n+1 , 0 );
REP( i , n ){
REP( j , 2 ){
sum[j][i+1] = sum[j][i] + t[j][i];
}
}
d[1] = yuyu( 1 , 0 , n );
d[0] = yuyu( 0 , 0 , n );
assert( d[0][n] == d[1][n] );
REP( i , n ){
nu[i] = d[0][i] + d[1][n-1-i];
}
REP( i , n ){
u[i] = -INFLL;
}
rec( 0 , n );
q = in();
REP( qc , q ){
ll p = in() - 1;
ll x = in();
ll ans = max( nu[p] , u[p] + t[0][p] - x );
printf( "%lld\n" , ans );
}
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Contest with Drinks Hard |
User |
joisino |
Language |
C++14 (GCC 5.4.1) |
Score |
1400 |
Code Size |
3941 Byte |
Status |
AC |
Exec Time |
499 ms |
Memory |
38084 KB |
Compile Error
./Main.cpp: In function ‘ll in()’:
./Main.cpp:45:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
ll in(){ ll x; scanf( "%lld" , &x ); return x; }
^
./Main.cpp: In function ‘std::string stin()’:
./Main.cpp:46:66: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
char yuyushiki[1000010]; string stin(){ scanf( "%s" , yuyushiki ); return yuyushiki; }
^
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1400 / 1400 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt |
All |
subtask_1_high_equaly_01.txt, subtask_1_high_equaly_02.txt, subtask_1_high_equaly_03.txt, subtask_1_high_equaly_04.txt, subtask_1_high_rand_01.txt, subtask_1_high_rand_02.txt, subtask_1_high_rand_03.txt, subtask_1_high_rand_04.txt, subtask_1_killer_01.txt, subtask_1_killer_02.txt, subtask_1_low_equaly_01.txt, subtask_1_low_equaly_02.txt, subtask_1_low_equaly_03.txt, subtask_1_low_equaly_04.txt, subtask_1_low_rand_01.txt, subtask_1_low_rand_02.txt, subtask_1_low_rand_03.txt, subtask_1_low_rand_04.txt, subtask_1_max_high_equaly_01.txt, subtask_1_max_high_equaly_02.txt, subtask_1_max_high_equaly_03.txt, subtask_1_max_high_equaly_04.txt, subtask_1_max_high_rand_01.txt, subtask_1_max_high_rand_02.txt, subtask_1_max_high_rand_03.txt, subtask_1_max_high_rand_04.txt, subtask_1_max_low_equaly_01.txt, subtask_1_max_low_equaly_02.txt, subtask_1_max_low_equaly_03.txt, subtask_1_max_low_equaly_04.txt, subtask_1_max_low_rand_01.txt, subtask_1_max_low_rand_02.txt, subtask_1_max_low_rand_03.txt, subtask_1_max_low_rand_04.txt, subtask_1_max_rand_equaly_01.txt, subtask_1_max_rand_equaly_02.txt, subtask_1_max_rand_equaly_03.txt, subtask_1_max_rand_equaly_04.txt, subtask_1_max_rand_rand_01.txt, subtask_1_max_rand_rand_02.txt, subtask_1_max_rand_rand_03.txt, subtask_1_max_rand_rand_04.txt, subtask_1_min_rand_rand_01.txt, subtask_1_min_rand_rand_02.txt, subtask_1_rand_equaly_01.txt, subtask_1_rand_equaly_02.txt, subtask_1_rand_equaly_03.txt, subtask_1_rand_equaly_04.txt, subtask_1_rand_rand_01.txt, subtask_1_rand_rand_02.txt, subtask_1_rand_rand_03.txt, subtask_1_rand_rand_04.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
3 ms |
256 KB |
sample_02.txt |
AC |
3 ms |
256 KB |
subtask_1_high_equaly_01.txt |
AC |
230 ms |
23528 KB |
subtask_1_high_equaly_02.txt |
AC |
174 ms |
19248 KB |
subtask_1_high_equaly_03.txt |
AC |
23 ms |
384 KB |
subtask_1_high_equaly_04.txt |
AC |
276 ms |
20824 KB |
subtask_1_high_rand_01.txt |
AC |
223 ms |
22536 KB |
subtask_1_high_rand_02.txt |
AC |
159 ms |
14172 KB |
subtask_1_high_rand_03.txt |
AC |
220 ms |
21056 KB |
subtask_1_high_rand_04.txt |
AC |
261 ms |
21608 KB |
subtask_1_killer_01.txt |
AC |
3 ms |
256 KB |
subtask_1_killer_02.txt |
AC |
3 ms |
256 KB |
subtask_1_low_equaly_01.txt |
AC |
298 ms |
24776 KB |
subtask_1_low_equaly_02.txt |
AC |
259 ms |
29432 KB |
subtask_1_low_equaly_03.txt |
AC |
296 ms |
32248 KB |
subtask_1_low_equaly_04.txt |
AC |
137 ms |
14736 KB |
subtask_1_low_rand_01.txt |
AC |
211 ms |
13496 KB |
subtask_1_low_rand_02.txt |
AC |
202 ms |
19024 KB |
subtask_1_low_rand_03.txt |
AC |
151 ms |
11664 KB |
subtask_1_low_rand_04.txt |
AC |
298 ms |
23408 KB |
subtask_1_max_high_equaly_01.txt |
AC |
480 ms |
38084 KB |
subtask_1_max_high_equaly_02.txt |
AC |
490 ms |
38084 KB |
subtask_1_max_high_equaly_03.txt |
AC |
499 ms |
38084 KB |
subtask_1_max_high_equaly_04.txt |
AC |
485 ms |
38084 KB |
subtask_1_max_high_rand_01.txt |
AC |
485 ms |
38084 KB |
subtask_1_max_high_rand_02.txt |
AC |
480 ms |
38084 KB |
subtask_1_max_high_rand_03.txt |
AC |
478 ms |
38084 KB |
subtask_1_max_high_rand_04.txt |
AC |
482 ms |
38084 KB |
subtask_1_max_low_equaly_01.txt |
AC |
458 ms |
38084 KB |
subtask_1_max_low_equaly_02.txt |
AC |
459 ms |
38084 KB |
subtask_1_max_low_equaly_03.txt |
AC |
459 ms |
38084 KB |
subtask_1_max_low_equaly_04.txt |
AC |
464 ms |
38084 KB |
subtask_1_max_low_rand_01.txt |
AC |
482 ms |
38084 KB |
subtask_1_max_low_rand_02.txt |
AC |
467 ms |
38084 KB |
subtask_1_max_low_rand_03.txt |
AC |
467 ms |
38084 KB |
subtask_1_max_low_rand_04.txt |
AC |
452 ms |
38084 KB |
subtask_1_max_rand_equaly_01.txt |
AC |
474 ms |
38084 KB |
subtask_1_max_rand_equaly_02.txt |
AC |
477 ms |
38084 KB |
subtask_1_max_rand_equaly_03.txt |
AC |
474 ms |
38084 KB |
subtask_1_max_rand_equaly_04.txt |
AC |
473 ms |
38084 KB |
subtask_1_max_rand_rand_01.txt |
AC |
475 ms |
38084 KB |
subtask_1_max_rand_rand_02.txt |
AC |
480 ms |
38084 KB |
subtask_1_max_rand_rand_03.txt |
AC |
472 ms |
38084 KB |
subtask_1_max_rand_rand_04.txt |
AC |
485 ms |
38084 KB |
subtask_1_min_rand_rand_01.txt |
AC |
3 ms |
256 KB |
subtask_1_min_rand_rand_02.txt |
AC |
3 ms |
256 KB |
subtask_1_rand_equaly_01.txt |
AC |
14 ms |
768 KB |
subtask_1_rand_equaly_02.txt |
AC |
275 ms |
24128 KB |
subtask_1_rand_equaly_03.txt |
AC |
111 ms |
8576 KB |
subtask_1_rand_equaly_04.txt |
AC |
229 ms |
20720 KB |
subtask_1_rand_rand_01.txt |
AC |
352 ms |
32904 KB |
subtask_1_rand_rand_02.txt |
AC |
179 ms |
13936 KB |
subtask_1_rand_rand_03.txt |
AC |
318 ms |
30776 KB |
subtask_1_rand_rand_04.txt |
AC |
104 ms |
5504 KB |