제출 #341519

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
341519		Sprdalo	Divide and conquer (IZhO14_divide)	C++17	100 / 100	50 ms	12396 KiB

divide

#include <bits/stdc++.h>

using namespace std;

#define int ll
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pi> vp;
typedef vector<pl> vpl;

struct st{
    int x;
    int g;
    int d;
};

vi p, t;

template<int maxn>
struct segtree{
    struct node{
        int x, ind;

        node(int x = INT32_MIN, int ind = 0) : x(x), ind(ind) {}

        node& operator+= (const node& other){
            if (x < other.x){
                x = other.x;
                ind = other.ind;
            }
            return *this;
        }

        node operator+(const node& other){
            auto tmp = *this;
            return tmp += other;
        }
    };

    node a[2*maxn];

    void init(){
        int n = t.size();

        for (int i = 1; i <= maxn; ++i)
            a[i+maxn-1] = node{INT32_MIN, i};

        for (int i = 1; i < n; ++i)
            a[i+maxn-1] = node{t[i], i};

        for (int i = maxn-1; i > 0; --i)
            a[i] = a[2*i] + a[2*i+1];
    }

    node get(int x, int pos = 1, int l = 1, int r = maxn){
        if (a[pos].x < x) return node{0, -1};
        if (pos >= maxn) return a[pos];

        int mid = (l+r)/2;
        auto tmp = get(x, 2*pos+1, mid+1, r);

        if (!tmp.x && tmp.ind == -1)
            tmp = get(x, 2*pos, l, mid);

        return tmp;
    }
};

segtree<131072> drvo;

signed main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); 
    cout.tie(nullptr); 
    cerr.tie(nullptr);    

    int n, sol = 0;
    cin >> n;

    vector<st> a(n+1);
    for (int i = 1; i <= n; ++i){
        cin >> a[i].x >> a[i].g >> a[i].d;

        if (a[i].d >= 1)
            sol = max(sol, a[i].g);
    }

    p = vi(n+1); t = vi(n+1);
    vi d = {0};
    for (int i = 1; i <= n; ++i){
        p[i] = p[i-1] + a[i].g;
        d.push_back(d.back() + a[i].d);
        t[i] = d[i] - a[i].x;
    }
    drvo.init();

    for (int i = 1; i <= n; ++i){
        auto k = drvo.get(d[i-1]-a[i].x);

        sol = max(sol, p[k.ind] - p[i-1]);
    }

    cout << sol << '\n';
}

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