Submission #491506

#	Time	Username	Problem	Language	Result	Execution time	Memory
491506		Yazan_Alattar	Divide and conquer (IZhO14_divide)	C++14	48 / 100	1090 ms	9572 KiB

divide

#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <utility>
#include <cmath>
#include <assert.h>
#include <numeric>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 100007;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

ll n, x[M], g[M], d[M], seg[4 * M], lazy[4 * M], ans;

void push(int node, int l, int r)
{
    if(lazy[node] != 0){
        seg[node] += (r - l + 1) * lazy[node];
        if(l != r){
            lazy[2 * node] += lazy[node];
            lazy[2 * node + 1] += lazy[node];
        }
        lazy[node] = 0;
    }
    return;
}

void upd(int st, int en, ll v, int node = 1, int l = 1, int r = n)
{
    push(node, l, r);
    if(l > en || r < st) return;
    if(l >= st && r <= en){
        lazy[node] += v;
        push(node, l, r);
        return;
    }
    int mid = (l + r) / 2;
    upd(st, en, v, 2 * node, l, mid);
    upd(st, en, v, 2 * node + 1, mid + 1, r);
    seg[node] = max(seg[2 * node], seg[2 * node + 1]);
    return;
}

int get(int st, int en, int node = 1, int l = 1, int r = n)
{
    push(node, l, r);
    if(l > en || r < st || seg[node] < 0) return -1;
    if(l == r) return l;
    int mid = (l + r) / 2;
    int ret = get(st, en, 2 * node + 1, mid + 1, r);
    if(ret == -1) ret = get(st, en, 2 * node, l, mid);
    return ret;
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> x[i] >> g[i] >> d[i];
        g[i] += g[i - 1];
        d[i] += d[i - 1];
        upd(i, i, d[i] - x[i]);
    }
    for(int i = 1; i <= n; ++i){
        upd(i, n, x[i] - x[i - 1]);
        ans = max(ans, g[get(i, n)] - g[i - 1]);
        upd(i, n, -d[i] + d[i - 1]);
    }
    cout << ans << endl;
    return 0;
}
// Don't forget special cases. (n = 1?)
// Look for the constraints. (Runtime array? overflow?)

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