제출 #503171

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
503171		lukameladze	금 캐기 (IZhO14_divide)	C++14	100 / 100	78 ms	9200 KiB

divide

# include <bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pb push_back
using namespace std;
const int N = 3e5 + 5;
int  n,x[N],g[N],d[N],pr[N],pr1[N];
int tree[4*N],val,dist,ans,idx;
void build(int node,int le, int ri) {
    if (le == ri) {
        tree[node] = pr[le];
        return ;
    }
    int mid = (le + ri) / 2;
    build(2*node,le,mid);
    build(2 * node + 1, mid + 1, ri);
    tree[node] = max(tree[2*node], tree[2*node + 1]);
}
int getans(int node, int le, int ri, int start,int end, int val) {
    if (le > end || ri < start) return 0;
    int mid = (le + ri) / 2;
    if (le >= start && ri <= end) {
        if (tree[node] < val) return 0;
        if (le == ri) {
            return le; 
        }
        if (tree[2*node + 1] >= val) return getans(2*node + 1, mid + 1, ri, start,end,val);
        else return getans(2*node, le,mid, start,end,val);
    }
    return max(getans(2*node,le,mid,start,end,val), getans(2*node + 1,mid + 1, ri, start,end,val));
}
main() {
    std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    for (int i = 1; i <= n; i++) {
        cin>>x[i]>>g[i]>>d[i];
        if (i > 1) {
            dist = (x[i] - x[i - 1]);
            pr[i] = pr[i - 1] + d[i] - dist;
          //  update(1,1,n,i, pr[i]);
        }
        ans = max(ans,g[i]);
        pr1[i] = pr1[i - 1] + g[i];
    }
    build(1,1,n);
    for (int i = 1; i <= n; i++) {
        // pr[j] - pr[i] + d[i] >= 0    pr[j] >= pr[i] - d[i]
        val = pr[i] - d[i];
        // i + 1-----> n     >=  val
        idx = getans(1,1,n,i + 1, n, val);
        if (idx == 0) {
            continue; 
        }
        ans = max(ans, pr1[idx] - pr1[i - 1]);
    }cout<<ans<<endl;
}

컴파일 시 표준 에러 (stderr) 메시지

divide.cpp:33:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   33 | main() {
      | ^~~~

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