oj.uz

Submission #86754

# Submission time Handle Problem Language Result Execution time Memory
86754 2018-11-27T09:24:13 Z karma Divide and conquer (IZhO14_divide) C++11
100 / 100
 72 ms 5600 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)
{
    char c;
    T sign = 1;
    x = 0;
    for (c = getchar(); c < '0' || c > '9'; c = getchar())
        if (c == '-')
            sign = -1;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    x *= sign;
}

typedef pair<int, int> pii;
typedef pair<ll, int> plli;
const int N = 2e5 + 7;

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

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

int Query(int x)
{
    if(x == 0) return Maxv;
    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]);
         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)
     {
         res = max(res, g[i] - g[i - 1]);
         int p = lower_bound(v.begin(), v.end(), r[i] - x[i]) - v.begin() + 1;
         int j = Query(p);
         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 3 ms 376 KB Output is correct
2 Correct 2 ms 440 KB Output is correct
3 Correct 2 ms 440 KB Output is correct
4 Correct 2 ms 440 KB Output is correct
5 Correct 2 ms 440 KB Output is correct
6 Correct 2 ms 440 KB Output is correct
7 Correct 2 ms 456 KB Output is correct
8 Correct 2 ms 456 KB Output is correct
9 Correct 2 ms 500 KB Output is correct
10 Correct 2 ms 500 KB Output is correct
11 Correct 2 ms 640 KB Output is correct
12 Correct 2 ms 640 KB Output is correct

Subtask #2
31.0 / 31.0

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

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1004 KB Output is correct
2 Correct 6 ms 1260 KB Output is correct
3 Correct 7 ms 1260 KB Output is correct
4 Correct 37 ms 3044 KB Output is correct
5 Correct 27 ms 3044 KB Output is correct
6 Correct 64 ms 5600 KB Output is correct
7 Correct 47 ms 5600 KB Output is correct
8 Correct 50 ms 5600 KB Output is correct
9 Correct 52 ms 5600 KB Output is correct
10 Correct 55 ms 5600 KB Output is correct
11 Correct 50 ms 5600 KB Output is correct
12 Correct 72 ms 5600 KB Output is correct