Submission #274890

#	Time	Username	Problem	Language	Result	Execution time	Memory
274890		lookcook	Divide and conquer (IZhO14_divide)	C++17	100 / 100	189 ms	33144 KiB

divide

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int maxn = (1<<18);
int tree[2*maxn];
void update(int k, int v) {
    for (int i = k+maxn; i >= 1; i /= 2) tree[i] = min(tree[i], v);
}
int query(int l, int r) {
    l += maxn, r += maxn;
    int res = 1e18;
    while (l <= r) {
        if (l%2==1) res = min(res, tree[l++]);
        if (r%2==0) res = min(res, tree[r--]);
        l /= 2, r /= 2;
    }
    return res;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    for (int i = 0; i < 2*maxn; i++) tree[i] = 1e18;
    int n;
    cin >> n;
    int x[n+1], g[n+1], e[n+1];
    x[0] = g[0] = e[0] = 0;
    set<int> s;
    for (int i = 1; i <= n; i++) {
        int xi, gi, ei;
        cin >> xi >> gi >> ei;
        x[i] = xi;
        g[i] = g[i-1] + gi;
        e[i] = e[i-1] + ei;
        s.insert(x[i]-e[i-1]);
        s.insert(x[i]-e[i]);
    }
    vector<int> v(s.begin(), s.end());
    map<int,int> m;
    for (int i = 0; i < v.size(); i++) m[v[i]] = i;
    int best = 0;
    for (int r = 1; r <= n; r++) {
        update(m[x[r]-e[r-1]], g[r-1]);
        int res = g[r]-query(m[x[r]-e[r]], maxn-1);
        best = max(best, res);
    }
    cout << best << '\n';
}

Compilation message (stderr)

divide.cpp: In function 'int main()':
divide.cpp:43:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 0; i < v.size(); i++) m[v[i]] = i;
      |                     ~~^~~~~~~~~~

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