| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 799028 | 2023-07-31T08:49:21 Z | vjudge1 | Candies (JOI18_candies) | C++17 | 2 ms | 1492 KB |
#include <bits/stdc++.h>
using namespace std;
#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define fi first
#define se second
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"
const int N = 2e5 + 9 , mod = 1e9 + 7;
ll d[N][2] = {} , a[N] = {}, dp[N] = {}, b[N] , c[N][5]= {} , sp[20][N][2];
ll ans = 0 , cnt = 0;
ll query(int L, int R , int k){
int j = 0 , i =1;
while(i * 2 <= (R - L + 1))
j++ , i *= 2;
if(sp[j][L][k] <= sp[j][R - (1 << j) + 1][k])
return sp[j][L][k];
else
return sp[j][R - (1 << j) + 1][k];
}
ll n;
ll get(int x , int y){
ll f ,l , r , k , ans1 = max( d[y][0] - d[x - 1][0] , d[y][1] - d[x - 1][1]);
f = d[y][x % 2] - d[x - 1][x % 2];
l = query(x , y , x % 2) ;
r = 0;
if(y != n)
l -= (d[n][x % 2] - d[y][(x % 2)]) - (d[n][1 - (x % 2)] - d[y][1 - (x % 2)]);
//cout<<"# "<<x<<" "<<y<<" "<<f - l<<" "<<f<<" "<<l<<" "<<"\n";
//if(x == 1 && y == 8)
// cout<<f<<"\n";
ans1 = max(ans1 ,f - l);
return ans1;
}
void del(int x ,int y){
if((y - x + 1) % 2 == 0)
ans -= get(x , y);
else
ans -= d[y][y % 2] - d[x - 1][y % 2];
cnt -= (y - x + 1) / 2;
cnt -= (y - x + 1) % 2;
}
void add(int x ,int y){
if((y- x + 1) % 2 == 0)
ans += get(x , y);
else
ans += d[y][y % 2] - d[x - 1][y % 2];
cnt += (y - x + 1) / 2;
cnt += (y - x + 1) % 2;
}
void solve(){
ll q , i , j , m , z , s = 0, f, l , r , k , x = 0 , y , mn = 1e18 , mx = -1;
cin>>n;
multiset<pair<ll,ll>>st ;
multiset<ll>s1 , s2;
vector<pair<ll,ll>>v;
for(i = 1; i <= n; i++){
cin>>a[i];
b[i] = 0;
d[i][0] = d[i - 1][0];
d[i][1] = d[i - 1][1];
d[i][i % 2] += a[i];
v.pb({a[i] , i});
}
for(i = 0; i < 20; i++)
for(j = 0; j <= n + 2; j++)
sp[i][j][0] = sp[i][j][1] = 1e18;
for(i = n; i >= 1; i--){
b[i % 2] += a[i];
c[i][i %2] = b[i % 2] - b[1 - (i % 2)];
}
b[0] = b[1] = 0;
for(i = 1; i <= n; i++)
sp[0][i][i % 2] = c[i][i % 2];
for(int i = 1; i <= 19; i++)
for(int j = 1; j + (1 << i) <= (n + 2); j++){
sp[i][j][0] = min(sp[i - 1][j][0], sp[i - 1][j + (1 << (i - 1))][0]);
sp[i][j][1] = min(sp[i - 1][j][1], sp[i - 1][j + (1 << (i - 1))][1]);
}
sort(rall(v));
for(auto to : v){
i = to.se;
if(s1.find(i -1) != s1.end() && s1.find(i + 1) != s1.end()){
auto it = st.lower_bound({i , 0});
y = it->se;
del(it->fi , it->se);
it--;
x = it->fi;
del(it->fi, it->se);
add(x , y);
st.erase({x , i - 1});
st.erase({i + 1 , y});
st.insert({x , y});
}else if(s1.find(i - 1) != s1.end()){
auto it = st.lower_bound({i , 0});
it--;
del(it->fi, it->se);
add(it->fi , i);
x = it->fi;
st.erase(it);
st.insert({x , i});
}else if(s1.find(i + 1) != s1.end()){
auto it = st.lower_bound({i , 0});
del(it->fi, it->se);
add(i , it->se);
y = it->se;
st.erase(it);
st.insert({i , y});
}else {
add(i, i);
st.insert({i , i});
}
s1.insert(i);
b[cnt] = max(b[cnt] , ans);
}
for(i = 1; i <= n / 2 + n % 2; i++)
cout<<b[i]<<"\n";
}
int main(){
TL;
/*
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
*/
int t = 1;
//cin>>t;
while(t--)
{
solve();
}
}
// Author : حسن
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 2 ms | 1492 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 2 ms | 1492 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |