oj.uz

Submission #491504

# Submission time Handle Problem Language Result Execution time Memory
491504 2021-12-02T18:18:49 Z Yazan_Alattar Divide and conquer (IZhO14_divide) C++14
0 / 100
 1 ms 460 KB 
#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, int 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];
        ++x[i];
        g[i] += g[i - 1];
        d[i] += d[i - 1];
        upd(i, i, d[i] - x[i]);
    }
    x[0] = 1;
    for(int i = 1; i <= n; ++i){
        assert(get(i, n) != -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
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Runtime error 1 ms 460 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Runtime error 1 ms 460 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Runtime error 1 ms 460 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -