Submission #798859

#	Time	Username	Problem	Language	Result	Execution time	Memory
798859		vjudge1	Candies (JOI18_candies)	C++17	0 / 100	2 ms	468 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];

ll ans = 0 , cnt = 0;

void del(int x ,int y){
    if((y - x + 1) % 2 == 0)
        ans -= max(d[y][0] - d[x - 1][0] , d[y][1] - d[x - 1][1]);
    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 += max(d[y][0] - d[x - 1][0] , d[y][1]- d[x - 1][1]);
    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 ,n, 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];
        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});
    }
    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.upper_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 (stderr)

candies.cpp: In function 'void solve()':
candies.cpp:46:8: warning: unused variable 'q' [-Wunused-variable]
   46 |     ll q , i , j , m ,n, z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
      |        ^
candies.cpp:46:16: warning: unused variable 'j' [-Wunused-variable]
   46 |     ll q , i , j , m ,n, z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
      |                ^
candies.cpp:46:20: warning: unused variable 'm' [-Wunused-variable]
   46 |     ll q , i , j , m ,n, z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
      |                    ^
candies.cpp:46:26: warning: unused variable 'z' [-Wunused-variable]
   46 |     ll q , i , j , m ,n, z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
      |                          ^
candies.cpp:46:30: warning: unused variable 's' [-Wunused-variable]
   46 |     ll q , i , j , m ,n, z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
      |                              ^
candies.cpp:46:38: warning: unused variable 'f' [-Wunused-variable]
   46 |     ll q , i , j , m ,n, z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
      |                                      ^
candies.cpp:46:41: warning: unused variable 'l' [-Wunused-variable]
   46 |     ll q , i , j , m ,n, z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
      |                                         ^
candies.cpp:46:45: warning: unused variable 'r' [-Wunused-variable]
   46 |     ll q , i , j , m ,n, z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
      |                                             ^
candies.cpp:46:49: warning: unused variable 'k' [-Wunused-variable]
   46 |     ll q , i , j , m ,n, z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
      |                                                 ^
candies.cpp:46:65: warning: unused variable 'mn' [-Wunused-variable]
   46 |     ll q , i , j , m ,n, z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
      |                                                                 ^~
candies.cpp:46:78: warning: unused variable 'mx' [-Wunused-variable]
   46 |     ll q , i , j , m ,n, z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
      |                                                                              ^~

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