oj.uz

Submission #37840

# Submission time Handle Problem Language Result Execution time Memory
37840 2017-12-28T09:15:10 Z mirbek01 Divide and conquer (IZhO14_divide) C++14
100 / 100
 179 ms 57732 KB 
# include <bits/stdc++.h>

# define pb push_back
# define fr first
# define sc second
# define mk make_pair

using namespace std;

const int inf = 1e9 + 7;
const int N = 1e5 + 5;

typedef long long ll;

int n, a[N];
ll ans, b[N], c[N], cb[N], cc[N], s1, s2;
vector < pair <ll, ll> > t[N * 4];

void Merge(vector < pair <ll, ll> > a, vector < pair <ll, ll> > b, vector < pair <ll, ll> > &c)
{
      int i = 0, j = 0;
      while(i < a.size() && j < b.size())
            if(a[i] < b[j])
                  c.pb(a[i ++]);
            else
                  c.pb(b[j ++]);

      while(i < a.size())
            c.pb(a[i ++]);
      while(j < b.size())
            c.pb(b[j ++]);

      for(int i = c.size() - 2; i >= 0; i --)
            c[i].sc = max(c[i].sc, c[i + 1].sc);
}

void build(int v = 1, int tl = 1, int tr = n)
{
      if(tl == tr)
            t[v].pb(mk(c[tl], b[tl]));
      else
      {
            int tm = (tl + tr) >> 1;
            build(v << 1, tl, tm);
            build((v << 1) |  1, tm + 1, tr);
            Merge(t[v << 1], t[(v << 1) | 1], t[v]);
      }
}

ll get(int pos, int v = 1, int tl = 1, int tr = n)
{
      if(tr < pos) return 0;

      if(pos <= tl)
      {
//            cout << tl << " OK " << tr << " " << t[v].back().fr - s2 << endl;
            if(t[v].back().fr - s2 + a[pos] < 0) return 0;
            int lo = 0, hi = t[v].size() - 1;
            while(hi - lo > 1)
            {
                  int md = (lo + hi) >> 1;
                  if(t[v][md].fr - s2 + a[pos] >= 0)
                        hi = md;
                  else
                        lo = md;
            }

            if(t[v][lo].fr - s2 + a[pos] >= 0) hi = lo;

            return t[v][hi].sc;
      }

      int tm = (tl + tr) >> 1;

      return max(get(pos, v << 1, tl, tm), get(pos, (v << 1) |  1, tm + 1, tr));
}

int main()
{
      scanf("%d", &n);

      for(int i = 1; i <= n; i ++)
      {
            scanf("%d %lld %lld", &a[i], &b[i], &c[i]);
            cb[i] = b[i];
            cc[i] = c[i];
            b[i] += b[i - 1];
            c[i] += c[i - 1];
      }

      for(int i = 1; i <= n; i ++)
            c[i] -= a[i];

      build();

      for(int i = 1; i <= n; i ++)
      {
            ans = max(ans, get(i) - s1);
//            cout << get(i) - s1 << endl;
//            for(int j = i; j <= n; j ++)
//            {
//                  ll res = b[j] - s1, sum = c[j] - s2;
//                  if(sum + a[i] < 0) continue;
//                  ans = max(ans, res);
//            }
            s1 += cb[i];
            s2 += cc[i];
      }

      printf("%lld", ans);
}

Compilation message

divide.cpp: In function 'void Merge(std::vector<std::pair<long long int, long long int> >, std::vector<std::pair<long long int, long long int> >, std::vector<std::pair<long long int, long long int> >&)':
divide.cpp:22:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while(i < a.size() && j < b.size())
               ^
divide.cpp:22:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while(i < a.size() && j < b.size())
                               ^
divide.cpp:28:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while(i < a.size())
               ^
divide.cpp:30:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while(j < b.size())
               ^
divide.cpp: In function 'int main()':
divide.cpp:80:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &n);
                      ^
divide.cpp:84:55: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %lld %lld", &a[i], &b[i], &c[i]);
                                                       ^

Subtask #1
17.0 / 17.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14912 KB Output is correct
2 Correct 0 ms 14912 KB Output is correct
3 Correct 0 ms 15044 KB Output is correct
4 Correct 3 ms 15176 KB Output is correct
5 Correct 3 ms 15176 KB Output is correct
6 Correct 6 ms 15316 KB Output is correct
7 Correct 6 ms 15176 KB Output is correct
8 Correct 6 ms 15176 KB Output is correct
9 Correct 6 ms 15452 KB Output is correct
10 Correct 6 ms 15452 KB Output is correct
11 Correct 6 ms 16876 KB Output is correct
12 Correct 9 ms 16876 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16876 KB Output is correct
2 Correct 13 ms 19096 KB Output is correct
3 Correct 23 ms 19096 KB Output is correct
4 Correct 96 ms 35404 KB Output is correct
5 Correct 93 ms 35404 KB Output is correct
6 Correct 176 ms 57732 KB Output is correct
7 Correct 173 ms 57732 KB Output is correct
8 Correct 179 ms 57732 KB Output is correct
9 Correct 159 ms 57732 KB Output is correct
10 Correct 179 ms 57732 KB Output is correct
11 Correct 173 ms 57732 KB Output is correct
12 Correct 169 ms 57732 KB Output is correct