oj.uz

Submission #384668

# Submission time Handle Problem Language Result Execution time Memory
384668 2021-04-02T04:02:36 Z zoooma13 Divide and conquer (IZhO14_divide) C++14
0 / 100
 1 ms 384 KB 
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    scanf("%d",&n);
    vector <array<int64_t ,3>> a(n);
    for(auto&x : a)
        scanf("%lld%lld%lld",&x[0],&x[1],&x[2]);
    a.insert(a.begin() ,{0,0,0});
    set <pair<int ,int>> ss;
    int64_t ans = 0;
    for(int i=1; i<=n; i++){
        ans = max(ans ,a[i][1]);
        a[i][1] += a[i-1][1];
        a[i][2] += a[i-1][2];

        auto it = ss.upper_bound({a[i][2] - a[i][0] ,0});
        if(it != ss.begin()){
            it = prev(it);
            ans = max(ans ,a[i][1] - it->second);
        }

        it = ss.insert({a[i-1][2] - a[i][0] ,a[i-1][1]}).first;
        if(it == ss.begin() || prev(it)->second > it->second){
            while(next(it) != ss.end() && next(it)->second >= it->second)
                ss.erase(next(it));
        }else{
            ss.erase(it);
        }
        ///a[i][2] - a[i][0] >= a[j][2] - a[j][0]
    }
    printf("%lld\n",ans);
}

Compilation message

divide.cpp: In function 'int main()':
divide.cpp:10:19: warning: format '%lld' expects argument of type 'long long int*', but argument 2 has type 'std::array<long int, 3>::value_type*' {aka 'long int*'} [-Wformat=]
   10 |         scanf("%lld%lld%lld",&x[0],&x[1],&x[2]);
      |                ~~~^
      |                   |
      |                   long long int*
      |                %ld
divide.cpp:10:23: warning: format '%lld' expects argument of type 'long long int*', but argument 3 has type 'std::array<long int, 3>::value_type*' {aka 'long int*'} [-Wformat=]
   10 |         scanf("%lld%lld%lld",&x[0],&x[1],&x[2]);
      |                    ~~~^
      |                       |
      |                       long long int*
      |                    %ld
divide.cpp:10:27: warning: format '%lld' expects argument of type 'long long int*', but argument 4 has type 'std::array<long int, 3>::value_type*' {aka 'long int*'} [-Wformat=]
   10 |         scanf("%lld%lld%lld",&x[0],&x[1],&x[2]);
      |                        ~~~^
      |                           |
      |                           long long int*
      |                        %ld
divide.cpp:34:16: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int64_t' {aka 'long int'} [-Wformat=]
   34 |     printf("%lld\n",ans);
      |             ~~~^    ~~~
      |                |    |
      |                |    int64_t {aka long int}
      |                long long int
      |             %ld
divide.cpp:7:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    7 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
divide.cpp:10:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   10 |         scanf("%lld%lld%lld",&x[0],&x[1],&x[2]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Incorrect 1 ms 364 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Incorrect 1 ms 364 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Incorrect 1 ms 364 KB Output isn't correct
7 Halted 0 ms 0 KB -