Submission #86734

#	Time	Username	Problem	Language	Result	Execution time	Memory
86734		HellAngel	Divide and conquer (IZhO14_divide)	C++14	100 / 100	174 ms	19576 KiB

divide

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 3e5 + 7;
int n, m, x[maxn], g[maxn], r[maxn];
int BIT[maxn], cnt, ans;
vector<int> vt;

map<int, int> mp;

void Update(int x, int val)
{
    for(; x < maxn; x += (x & -x))
    {
        BIT[x] = min(BIT[x], val);
    }
}

int Get(int x)
{
    int ans = INT_MAX;
    for(; x > 0; x -= (x & -x))
    {
        ans = min(ans, BIT[x]);
    }
    return ans;
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("test.inp", "r", stdin);
    //freopen("test.out", "w", stdout);
    fill_n(BIT, maxn, INT_MAX);
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> x[i] >> g[i] >> r[i];
        ans = max(ans, g[i]);
        r[i] += r[i - 1];
        g[i] += g[i - 1];
        vt.push_back(r[i] - x[i]);
        vt.push_back(r[i - 1] - x[i]);
    }
    sort(vt.begin(), vt.end());
    mp[vt[0]] = ++cnt;
    for(int i = 1; i < vt.size(); i++)
    {
        if(vt[i] == vt[i - 1]) continue;
        mp[vt[i]] = ++cnt;
    }
    for(int i = 1; i <= n; i++)
    {
        int gau = mp[r[i] - x[i]];
        int meo = mp[r[i - 1] - x[i]];
        int hihi = Get(gau);
        if(hihi != INT_MAX) ans = max(ans, g[i] - g[hihi - 1]);
        Update(meo, i);
    }
    cout << ans;
}

Compilation message (stderr)

divide.cpp: In function 'int32_t main()':
divide.cpp:48:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i < vt.size(); i++)
                    ~~^~~~~~~~~~~

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