oj.uz

Submission #103008

# Submission time Handle Problem Language Result Execution time Memory
103008 2019-03-28T15:05:53 Z brcode Divide and conquer (IZhO14_divide) C++14
100 / 100
 216 ms 8696 KB 
#include <iostream>

using namespace std;
const long long MAXN = 1e5+5;
long long tree[4*MAXN];
long long x[MAXN];
long long g[MAXN];
long long d[MAXN];
long long s[MAXN];
long long tog[MAXN];
void build(long long curr,long long l,long long r){
    if(l==r){
        tree[curr] = s[l-1]-x[l];
    }else{
        long long mid = (l+r)/2;
        build(2*curr,l,mid);
        build(2*curr+1,mid+1,r);
        tree[curr] = min(tree[2*curr],tree[2*curr+1]);
    }
    
}
long long query(long long curr,long long l,long long r,long long val){
    if(l == r){
        if(tree[curr] <=val){
            return l;
        }else{
            return 1e9;
        }
    }else{
        long long mid = (l+r)/2;
        if(tree[2*curr]<=val){
            return query(2*curr,l,mid,val);
        }else{
            return query(2*curr+1,mid+1,r,val);
        }
    }
}
int main(){
    long long n;
    cin>>n;
    for(long long i=1;i<=n;i++){
        cin>>x[i]>>g[i]>>d[i];
        s[i] = s[i-1]+d[i];
        tog[i] = tog[i-1]+g[i];
    }
    build(1,1,n);
    long long ans = tog[1];
    for(long long i=1;i<=n;i++){
        long long pos = query(1,1,n,s[i]-x[i]);
        if(pos!=1e9){
            ans = max(ans,tog[i]-tog[pos-1]);
        }
    }
    cout<<ans<<endl;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 300 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 352 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 2 ms 484 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 4 ms 480 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 4 ms 512 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 11 ms 768 KB Output is correct
12 Correct 9 ms 768 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 768 KB Output is correct
2 Correct 11 ms 1152 KB Output is correct
3 Correct 19 ms 1116 KB Output is correct
4 Correct 64 ms 4344 KB Output is correct
5 Correct 72 ms 4728 KB Output is correct
6 Correct 216 ms 8504 KB Output is correct
7 Correct 123 ms 8056 KB Output is correct
8 Correct 140 ms 8184 KB Output is correct
9 Correct 164 ms 7992 KB Output is correct
10 Correct 106 ms 8056 KB Output is correct
11 Correct 149 ms 8564 KB Output is correct
12 Correct 170 ms 8696 KB Output is correct