Submission #1173228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173228		DangKhoizzzz	Divide and conquer (IZhO14_divide)	C++17	100 / 100	35 ms	8380 KiB

divide

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair <int , int>
#define arr3 array <int , 3>

using namespace std;

const int INF = 1e18 + 7;
const int maxn = 2e5 + 7;

int n , pre[maxn] , pre1[maxn] , pre2[maxn];
arr3 a[maxn];

struct Fenwick_Tree
{
    vector <int> bit;

    void init() {bit.assign(maxn+5 , INF);}

    void update(int pos , int val)
    {
        while(pos < maxn)
        {
            bit[pos] = min(bit[pos] , val);
            pos += (pos & (-pos));
        }
    }

    int get(int pos)
    {
        int res = INF;
        while(pos > 0)
        {
            res = min(res , bit[pos]);
            pos -= (pos & (-pos));
        }
        return res;
    }
};

Fenwick_Tree BIT;

vector <int> val;

void compress()
{
    sort(val.begin() , val.end());
    val.erase(unique(val.begin() , val.end()) , val.end());
    for(int i = 1; i <= n; i++)
    {
        pre1[i] = upper_bound(val.begin() , val.end() , pre1[i]) - val.begin();
        pre2[i] = upper_bound(val.begin() , val.end() , pre2[i]) - val.begin();
    }
}

void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i][0] >> a[i][1] >> a[i][2];
    }
    sort(a+1 , a+n+1);
    BIT.init();

    for(int i = 1; i <= n; i++)
    {
        pre1[i] = (pre[i-1] - a[i][0]);
        pre[i] = pre[i-1] + a[i][2];
        pre2[i] = (pre[i] - a[i][0]);
        val.push_back(pre1[i]);
        val.push_back(pre2[i]);
    }

    compress();

    //for(int i = 1; i <= n; i++) cout << pre1[i] << ' '; cout << '\n';
    //for(int i = 1; i <= n; i++) cout << pre2[i] << ' '; cout << '\n';

    int preg = 0;
    int ans = 0;

    for(int i = 1; i <= n; i++)
    {
        BIT.update(pre1[i] , preg);
        preg += a[i][1];
        ans = max(ans , preg - BIT.get(pre2[i]));
    }

    cout << ans << '\n';
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

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