Submission #336679

#	Time	Username	Problem	Language	Result	Execution time	Memory
336679		mehrdad_sohrabi	Candies (JOI18_candies)	C++14	100 / 100	2083 ms	515928 KiB

candies

#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
#define endl '\n'
#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
using namespace std;
const int N=2e5+100;
vector <pii> seg[2][2][N*4];
ll a[N];
void build(ll nod,ll l,ll r){
    if (r-l==1){
        seg[1][1][nod].pb({1,a[l]});
        seg[0][0][nod].pb({0,0});
        return ;
    }
    ll mid=(r+l)/2;
    build(nod*2,l,mid);
    build(nod*2+1,mid,r);
  //  cout << "KIR" << " " << l << " " << r << endl;
    for (int l1=0;l1<=1;l1++){
        for (int r1=0;r1<=1;r1++){
            for (int l2=0;l2<=1;l2++){
                for (int r2=0;r2<=1;r2++){
                    if (r1==1 && l2==1) continue;
                    vector <pii> a=seg[l1][r1][nod*2],b=seg[l2][r2][nod*2+1];
                    a.pb({0,(ll)-1e18});
                    b.pb(a.back());
                    ll p1=0,p2=0;
                   // cout << l1 << " " << r1 << " " << l2 << " " << r2 << endl;
                    while(p1<a.size()-1 && p2<b.size()-1){
                        seg[l1][r2][nod].pb({a[p1].F+b[p2].F,a[p1].S+b[p2].S});
                        if (a[p1+1].S-a[p1].S>b[p2+1].S-b[p2].S) p1++;
                        else p2++;
                    }
                }
            }
        }
    }
  //  cout << "KOS" << endl;
    for (int l1=0;l1<2;l1++){
        for (int r1=0;r1<2;r1++){
            sort(seg[l1][r1][nod].begin(),seg[l1][r1][nod].end());
            vector <pii> a=seg[l1][r1][nod],b;
            reverse(a.begin(),a.end());
            if (a.size()==0){
       //         cout << l << " " << r << " " << l1 << " " << r1 << endl;
                continue;
            }
            b.pb(a[0]);
            for (int i=1;i<a.size();i++){
                if (a[i].F==a[i-1].F) continue;
                b.pb(a[i]);
            }
            reverse(b.begin(),b.end());
            seg[l1][r1][nod]=b;
        }
    }
}
ll ans[N];
int32_t main(){
    ll n;
    cin >> n;
    for (int i=1;i<=n;i++){
        cin >> a[i];
    }
    build(1,1,n+1);
    for (int l=0;l<2;l++){
        for (int r=0;r<2;r++){
            for (auto u : seg[l][r][1]){
                ans[u.F]=max(ans[u.F],u.S);
            }
        }
    }
    for (int i=1;i<=(n+1)/2;i++){
        cout << ans[i] << endl;
    }
}

Compilation message (stderr)

candies.cpp: In function 'void build(ll, ll, ll)':
candies.cpp:37:29: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |                     while(p1<a.size()-1 && p2<b.size()-1){
      |                           ~~^~~~~~~~~~~
candies.cpp:37:46: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |                     while(p1<a.size()-1 && p2<b.size()-1){
      |                                            ~~^~~~~~~~~~~
candies.cpp:57:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |             for (int i=1;i<a.size();i++){
      |                          ~^~~~~~~~~

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