Submission #198807

#	Time	Username	Problem	Language	Result	Execution time	Memory
198807		Vladikus004	Divide and conquer (IZhO14_divide)	C++14	100 / 100	139 ms	22760 KiB

divide

#include <bits/stdc++.h>
#define inf 2e9
#define ff first
#define ss second
#define all(v) v.begin() , v.end()
#define int long long
using namespace std;
typedef long long ll;
typedef pair <ll, int> pii;

const int N = 100000 + 5;

struct obj{
    int x, d, g;
    obj(){
        x = g = d = 0;
    }
};

int n;
ll pref[N], fenw[2 * N], pref_g[N];
obj a[N];

void up(int ind, ll x){
    for (int i = ind; i <= 2 * N; i |= i + 1)
        fenw[i] = min(fenw[i], x);
}

ll get_min(int ind){
    ll ans = inf;
    for (int i = ind; i >= 0; i = (i & (i + 1)) - 1)
        ans = min(ans, fenw[i]);
    return ans;
}

void init(){
    for (int i = 0; i <= 2 * N; i++)
        fenw[i] = inf;
}

map <ll, int> code;

int32_t main()
{
//    #ifdef VBH
//        freopen("input.txt" , "r" , stdin);
//    #endif
//        freopen("divide.in" , "r" , stdin);
//        freopen("divide.out" , "w" , stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    init();
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i].x >> a[i].g >> a[i].d;
    for (int i = 1; i <= n; i++){
        pref_g[i] = a[i].g;
        pref_g[i] += pref_g[i - 1];
        pref[i] = a[i].d;
        pref[i] += pref[i - 1];
    }
    vector <ll> roman;
    for (int i = 1; i <= n; i++){
        roman.push_back(-a[i].x + pref[i]);
        roman.push_back(-a[i].x + pref[i - 1]);
    }
    sort(roman.begin(), roman.end());
    for (int i = 0; i < (int)roman.size(); i++)
        code[roman[i]] = i;
    ll ans = 0;
    for (int i = 1; i <= n; i++){
        ans = max(ans, (ll)a[i].g);
        int ind = code[-a[i].x + pref[i]];
        ll mn = get_min(ind);
        if (mn != inf)
            ans = max(ans, pref_g[i] - pref_g[mn - 1]);
        ind = code[-a[i].x + pref[i - 1]];
        up(ind, i);
    }
    cout << ans;
    return 0;
}

Compilation message (stderr)

divide.cpp: In function 'void init()':
divide.cpp:38:17: warning: iteration 200010 invokes undefined behavior [-Waggressive-loop-optimizations]
         fenw[i] = inf;
                 ^
divide.cpp:37:23: note: within this loop
     for (int i = 0; i <= 2 * N; i++)
                     ~~^~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52