Submission #800435

#	Time	Username	Problem	Language	Result	Execution time	Memory
800435		vjudge1	Candies (JOI18_candies)	C++17	0 / 100	2 ms	596 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] = {} , a[N] = {}, dp[N][2] = {}, b[N] ,c[N] ,  sq = 310;

multiset<pair<ll,pair<ll,ll>>>st , st1;


void del(int x , int y , int z){
    st1.erase({x ,{y , z}});
    st.erase({z ,{x , y}});
}

void add(int x , int y , int z){
    st1.insert({x ,{y , z}});
    st.insert({z ,{x , y}});
}


void solve(){
    ll q , i , j , m , n,  z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
    cin>>n;
    for(i = 1; i <= n; i++){
        cin>>a[i];
        dp[i][0] = dp[i - 1][0];
        dp[i][1] = dp[i - 1][1];
        dp[i][i % 2] += a[i];
        st.insert({a[i] ,{i , i}});
        st1.insert({i , {i , a[i]}});
    }
    l = 1 , r = n , s = 0;
    for(i = 1; i <= (n + 1) / 2; i++){
        auto it = st.rbegin();
        s += it->fi;
        z = it->fi , x = it->se.fi , y = it->se.se;
        del(x , y , z);
        cout<<s<<"\n";
        if(x == l || y == r){
            if(x == l){
                auto it1 = st1.lower_bound({y, {-1 , -1}});
                if(st1.size() && it1 != st1.end())
                    y = it1->se.fi , del(it1->fi , it1->se.fi,it1->se.se);
                l = y + 1;
            }
            if(y == r){
                auto it1 = st1.lower_bound({y , {-1 , -1}});
                if(st1.size() && it1 != st1.begin()){
                    it1--;
                    x = it1->fi;
                    del(it1->fi , it1->se.fi , it1->se.se);
                }
                r = x - 1;
            }
            continue;
        }
        auto it1 = st1.lower_bound({y , {-1 , -1}});
        if(st1.size() && it1 != st1.end()){
            y = it1->se.fi;
            del(it1->fi , it1->se.fi , it1->se.se);
        }
        it1 = st1.lower_bound({y , {-1 , -1}});
        if(st1.size() && it1 != st1.begin()){
            it1--;
            x = it1->fi;
            del(it1->fi , it1->se.fi , it1->se.se);
        }
        add(x , y , dp[y][x%2] - dp[x - 1][x%2] - (dp[y][1 - (x%2)] - dp[x - 1][1 - (x % 2)] ));
    }
}

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:41:8: warning: unused variable 'q' [-Wunused-variable]
   41 |     ll q , i , j , m , n,  z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
      |        ^
candies.cpp:41:16: warning: unused variable 'j' [-Wunused-variable]
   41 |     ll q , i , j , m , n,  z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
      |                ^
candies.cpp:41:20: warning: unused variable 'm' [-Wunused-variable]
   41 |     ll q , i , j , m , n,  z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
      |                    ^
candies.cpp:41:40: warning: unused variable 'f' [-Wunused-variable]
   41 |     ll q , i , j , m , n,  z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
      |                                        ^
candies.cpp:41:51: warning: unused variable 'k' [-Wunused-variable]
   41 |     ll q , i , j , m , n,  z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
      |                                                   ^
candies.cpp:41:67: warning: unused variable 'mn' [-Wunused-variable]
   41 |     ll q , i , j , m , n,  z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
      |                                                                   ^~
candies.cpp:41:80: warning: unused variable 'mx' [-Wunused-variable]
   41 |     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