oj.uz

Submission #86757

# Submission time Handle Problem Language Result Execution time Memory
86757 2018-11-27T09:30:01 Z karma Divide and conquer (IZhO14_divide) C++11
100 / 100
 59 ms 5504 KB 
#include<bits/stdc++.h>
#define For(i, a, b)  for(int i = a; i <= b; ++i)
#define Ford(i, a, b) for(int i = a; i >= b; --i)
#define Task          "test"
#define ld            long double
#define ll            long long
#define X             first
#define Y             second
#define pb            push_back
//#define Karma

using namespace std;

template <typename T> inline void Cin(T &x)
{
    register char c;
    for (c = getchar(); c < '0' || c > '9'; c = getchar());
    for (x = 0; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

const int N = 2e5 + 7;

ll x[N], g[N], r[N], res, j, p;
int t[N], n, Maxv;
vector<ll> v;

void Update(int x, int val)
{
     while(x <= Maxv)
     {
         t[x] = min(t[x], val);
         x += (x & -x);
     }
}

int Query(int x)
{
    int res = Maxv;
    while(x > 0)
    {
        res = min(res, t[x]);
        x -= (x & -x);
    }
    return res;
}

void Enter()
{
     Cin(n);
     Maxv = 2 * n + 2;
     fill_n(t, Maxv + 2, Maxv);
     For(i, 1, n)
     {
         Cin(x[i]), Cin(g[i]), Cin(r[i]);
         res = max(res, g[i]);
         g[i] += g[i - 1], r[i] += r[i - 1];
         v.pb(r[i - 1] - x[i]), v.pb(r[i] - x[i]);
     }
     sort(v.begin(), v.end());
     v.erase(unique(v.begin(), v.end()), v.end());
}

void Solve()
{
     For(i, 1, n)
     {
         j = Query(lower_bound(v.begin(), v.end(), r[i] - x[i]) - v.begin() + 1);
         if(j < Maxv) res = max(res, g[i] - g[j - 1]);
         p = lower_bound(v.begin(), v.end(), r[i - 1] - x[i]) - v.begin() + 1;
         Update(p, i);
     }
     cout << res;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
#ifdef Karma
    freopen(Task".inp", "r", stdin);
    freopen(Task".out", "w", stdout);
#endif // Karma

    Enter();
    Solve();

    return 0;

}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 500 KB Output is correct
3 Correct 2 ms 500 KB Output is correct
4 Correct 3 ms 500 KB Output is correct
5 Correct 2 ms 528 KB Output is correct
6 Correct 2 ms 544 KB Output is correct
7 Correct 2 ms 544 KB Output is correct
8 Correct 2 ms 544 KB Output is correct
9 Correct 2 ms 560 KB Output is correct
10 Correct 2 ms 560 KB Output is correct
11 Correct 2 ms 560 KB Output is correct
12 Correct 2 ms 648 KB Output is correct

Subtask #2
31.0 / 31.0

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

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1108 KB Output is correct
2 Correct 6 ms 1388 KB Output is correct
3 Correct 6 ms 1388 KB Output is correct
4 Correct 25 ms 3044 KB Output is correct
5 Correct 28 ms 3056 KB Output is correct
6 Correct 59 ms 5504 KB Output is correct
7 Correct 47 ms 5504 KB Output is correct
8 Correct 48 ms 5504 KB Output is correct
9 Correct 45 ms 5504 KB Output is correct
10 Correct 48 ms 5504 KB Output is correct
11 Correct 56 ms 5504 KB Output is correct
12 Correct 52 ms 5504 KB Output is correct