Submission #683779

#	Time	Username	Problem	Language	Result	Execution time	Memory
683779		NintsiChkhaidze	Divide and conquer (IZhO14_divide)	C++17	100 / 100	146 ms	23744 KiB

divide

#include <bits/stdc++.h>
#define ll long long
#define left (h<<1),l,((l+r)>>1)
#define right ((h<<1)|1),((l+r)>>1) + 1,r
#define pb push_back
#define int ll
using namespace std;

const int N = 200005,inf = 1e18;
map <int,int> mp;
int pe[N],pg[N],t[4*N],a[N];
vector <int> v;

void build(int h,int l,int r){
    t[h] = inf;
    if (l == r) return;
    build(left),build(right);
    t[h] = min(t[h*2],t[h*2+1]);
}
void upd(int h,int l,int r,int idx,int val){
    if (l == r){
        t[h] = min(t[h],val);
        return;
    }
    if ((l + r)/2 < idx) upd(right,idx,val);
    else upd(left,idx,val);
    t[h] = min(t[h*2],t[h*2+1]);
}

int get(int h,int l,int r,int L,int R){
    if (r < L || R < l) return inf;
    if (L <= l && r <= R) return t[h];
    return min(get(left,L,R),get(right,L,R));
}
signed main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
 
    int n;
    cin>>n;

    for (int i = 1; i <= n; i++){
        int g,e;
        cin>>a[i]>>g>>e;
        pe[i] = pe[i - 1] + e;
        pg[i] = pg[i - 1] + g;
        v.pb(pe[i] - a[i]);
        v.pb(pe[i - 1] - a[i]);
    }
    sort(v.begin(),v.end());
    for (int i=0;i<v.size();i++){
        if (!i) mp[v[i]] = 1;
        else if (v[i] == v[i - 1]) mp[v[i]] = mp[v[i - 1]];
        else mp[v[i]] = mp[v[i - 1]] + 1;
    }
    int lm = 200000,ans=0;
    build(1,1,lm);
    for (int i = 1; i <= n; i++){
        upd(1,1,lm,mp[pe[i - 1] - a[i]],i);
        int l = get(1,1,lm,1,mp[pe[i] - a[i]]);
        if (l != inf) ans=max(ans,pg[i] - pg[l - 1]);
    }
    cout<<ans;
}

Compilation message (stderr)

divide.cpp: In function 'int main()':
divide.cpp:50:19: 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]
   50 |     for (int i=0;i<v.size();i++){
      |                  ~^~~~~~~~~

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