oj.uz

Submission #68433

# Submission time Handle Problem Language Result Execution time Memory
68433 2018-08-17T06:54:52 Z yusufake Divide and conquer (IZhO14_divide) C++
48 / 100
 83 ms 15904 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5;

ll F[N],X[N],G[N],D[N],T[N+N],t,n,i,j,ans;

ll qry(int x){
    ll t = 1LL << 55;
    for(; x ; x -= x&-x)
        t = min(t , F[x]);
    return t;
}

void up(int x, ll a){
    for(; x <= t ; x += x&-x)
        F[x] = min(F[x] , a);
}

int main(){
    scanf("%lld",&n);
    for(i=1;i<=n;i++){
        scanf("%lld%lld%lld",&X[i],&G[i],&D[i]);
        G[i] += G[i-1];
        D[i] += D[i-1];
        T[++t] = D[i]-X[i];
        T[++t] = D[i-1]-X[i];
    }
    sort(T+1 , T+t+1);
    memset(F , 127 , sizeof F);
    for(i=1;i<=n;i++){
        j = lower_bound(T+1 , T+t+1 , D[i-1]-X[i]) - T;
        up(j,G[i-1]);
        j = lower_bound(T+1 , T+t+1 , D[i]-X[i]) - T;
        ans = max(ans , G[i] - qry(j));
    }

    printf("%lld", ans);
    return 0;
}

Compilation message

divide.cpp: In function 'int main()':
divide.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&n);
     ~~~~~^~~~~~~~~~~
divide.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld%lld",&X[i],&G[i],&D[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 3 ms 1212 KB Output is correct
3 Correct 3 ms 1212 KB Output is correct
4 Correct 3 ms 1256 KB Output is correct
5 Correct 4 ms 1304 KB Output is correct
6 Correct 4 ms 1304 KB Output is correct
7 Correct 3 ms 1304 KB Output is correct
8 Correct 2 ms 1304 KB Output is correct
9 Correct 3 ms 1312 KB Output is correct
10 Correct 3 ms 1360 KB Output is correct
11 Correct 3 ms 1360 KB Output is correct
12 Correct 4 ms 1360 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1360 KB Output is correct
2 Correct 3 ms 1388 KB Output is correct
3 Correct 3 ms 1388 KB Output is correct
4 Correct 3 ms 1388 KB Output is correct
5 Correct 3 ms 1392 KB Output is correct
6 Correct 4 ms 1392 KB Output is correct
7 Correct 3 ms 1392 KB Output is correct
8 Correct 4 ms 1392 KB Output is correct
9 Correct 5 ms 1392 KB Output is correct
10 Correct 5 ms 1392 KB Output is correct
11 Correct 8 ms 1516 KB Output is correct
12 Correct 6 ms 1516 KB Output is correct

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1516 KB Output is correct
2 Correct 9 ms 1772 KB Output is correct
3 Correct 10 ms 1900 KB Output is correct
4 Correct 43 ms 4572 KB Output is correct
5 Correct 52 ms 5988 KB Output is correct
6 Runtime error 83 ms 15904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -