Submission #798991

#	Time	Username	Problem	Language	Result	Execution time	Memory
798991		vjudge1	Candies (JOI18_candies)	C++17	0 / 100	2 ms	980 KiB

candies

#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 = (int)log2(R - L + 1);
    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 < 0)
        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];
        //c[i][i % 2] = d[i][i % 2] - d[i][1 - (i % 2)];
        v.pb({a[i] , i});
    }
    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][0] = c[i][0] , sp[0][i][1] = c[i][1];
    for(int i = 1; i <= 19; i++)
        for(int j = 1; j + (1 << i) <= n + 1; 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});
            //cout<<i<<" ";
            }
      //      cout<<i<<" "<<cnt<<" "<<ans<<"\n";
            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 (stderr)

candies.cpp: In function 'long long int get(int, int)':
candies.cpp:39:15: warning: variable 'r' set but not used [-Wunused-but-set-variable]
   39 |     ll f ,l , r ,  k , ans1 = max( d[y][0] - d[x - 1][0] , d[y][1] - d[x - 1][1]);
      |               ^
candies.cpp:39:20: warning: unused variable 'k' [-Wunused-variable]
   39 |     ll f ,l , r ,  k , ans1 = max( d[y][0] - d[x - 1][0] , d[y][1] - d[x - 1][1]);
      |                    ^
candies.cpp: In function 'void solve()':
candies.cpp:71:8: warning: unused variable 'q' [-Wunused-variable]
   71 |     ll q , i , j , m , z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
      |        ^
candies.cpp:71:16: warning: unused variable 'j' [-Wunused-variable]
   71 |     ll q , i , j , m , z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
      |                ^
candies.cpp:71:20: warning: unused variable 'm' [-Wunused-variable]
   71 |     ll q , i , j , m , z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
      |                    ^
candies.cpp:71:24: warning: unused variable 'z' [-Wunused-variable]
   71 |     ll q , i , j , m , z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
      |                        ^
candies.cpp:71:28: warning: unused variable 's' [-Wunused-variable]
   71 |     ll q , i , j , m , z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
      |                            ^
candies.cpp:71:36: warning: unused variable 'f' [-Wunused-variable]
   71 |     ll q , i , j , m , z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
      |                                    ^
candies.cpp:71:39: warning: unused variable 'l' [-Wunused-variable]
   71 |     ll q , i , j , m , z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
      |                                       ^
candies.cpp:71:43: warning: unused variable 'r' [-Wunused-variable]
   71 |     ll q , i , j , m , z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
      |                                           ^
candies.cpp:71:47: warning: unused variable 'k' [-Wunused-variable]
   71 |     ll q , i , j , m , z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
      |                                               ^
candies.cpp:71:63: warning: unused variable 'mn' [-Wunused-variable]
   71 |     ll q , i , j , m , z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
      |                                                               ^~
candies.cpp:71:76: warning: unused variable 'mx' [-Wunused-variable]
   71 |     ll q , i , j , m , z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
      |                                                                            ^~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 92