Submission #96219

#	Time	Username	Problem	Language	Result	Execution time	Memory
96219		Kastanda	Divide and conquer (IZhO14_divide)	C++11	100 / 100	58 ms	7664 KiB

divide

#include<bits/stdc++.h>
#define lc (id << 1)
#define rc (id << 1 ^ 1)
#define md ((l + r) >> 1)
using namespace std;
typedef long long ll;
const int N = 100005;
int n;
ll D[N], E[N], G[N], MN[N * 4];
void Build(int id = 1, int l = 0, int r = n + 1)
{
    if (r - l < 2)
    {
        MN[id] = D[l] - E[l];
        return ;
    }
    Build(lc, l, md);
    Build(rc, md, r);
    MN[id] = min(MN[lc], MN[rc]);
}
int Get(ll val, int id = 1, int l = 0, int r = n + 1)
{
    if (MN[id] > val)
        return (-1);
    if (r - l < 2)
        return (l);
    int i = Get(val, rc, md, r);
    if (i != -1) return (i);
    return (Get(val, lc, l, md));
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld%lld%lld", &D[i], &G[i], &E[i]);
        E[i] += E[i - 1]; G[i] += G[i - 1];
    }
    D[0] = -1e17;
    Build();
    ll Max = 0;
    for (int i = 1; i <= n; i++)
    {
        int j = Get(D[i] - E[i - 1]);
        if (j >= i)
            Max = max(Max, G[j] - G[i - 1]);
    }
    return !printf("%lld\n", Max);
}

Compilation message (stderr)

divide.cpp: In function 'int main()':
divide.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
divide.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld%lld", &D[i], &G[i], &E[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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