Submission #99371

#	Time	Username	Problem	Language	Result	Execution time	Memory
99371		kjain_1810	Divide and conquer (IZhO14_divide)	C++17	100 / 100	94 ms	11756 KiB

divide

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
typedef long double ld;
const int maxn = 1e5 + 5;
#define int ll
 
int n;
int x[maxn] , r[maxn] , g[maxn] , dis[maxn];
int bit[maxn] , cost[maxn] , c[maxn] , sum[maxn];
vector<pair<int,int>> v;
 
void update(int pos , int x)
{
    for( ; pos > 0 ; pos &= pos - 1)
        bit[pos] = min(bit[pos],x);
}
 
int query(int pos)
{
    int res = maxn;
    for( ; pos < maxn ; pos += pos & -pos)
        res = min(res , bit[pos]);
    return res;
}
 
int32_t main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 1 ; i <= n ; ++i)
        cin >> x[i] >> g[i] >> r[i];
    for(int i = 1 ; i <= n ; ++i){
        r[i] += r[i - 1];
        sum[i] = sum[i - 1] + g[i];
    }
    for(int i = 1 ; i <= n ; ++i)
        v.pb({x[i]-r[i-1],i});
    sort(v.begin(),v.end());
    int cnt = 1;
    c[v[0].second] = 1;
    vector<pair<int,int>> v1;
    v1.push_back(v[0]);
    for(int i = 1 ; i < v.size() ; ++i)
    {
        if(v[i].first == v[i - 1].first)c[v[i].second] = cnt;
        else c[v[i].second] = ++cnt ,v1.push_back(v[i]);
    }
    v = v1;
    fill_n(bit , maxn , maxn);
    ll res = 0;
    for(int i = 1 ; i <= n ; ++i)
    {
        update(c[i] , i - 1);
        int pos = lower_bound(v.begin(),v.end(),make_pair(x[i] - r[i] , 0ll)) - v.begin();
        int ans = query(pos + 1);
//        cout << ans << " ";
        if(ans != maxn)res = max(res , sum[i] - sum[ans]);
//        res = max(res , g[i]);
    }
    cout << res;
}

Compilation message (stderr)

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

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