oj.uz

Submission #86747

# Submission time Handle Problem Language Result Execution time Memory
86747 2018-11-27T09:05:19 Z karma Divide and conquer (IZhO14_divide) C++11
100 / 100
 57 ms 6256 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, t[N], n;
vector<ll> v;

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

ll Query(ll x)
{
    if(x == 0) return 5 * n;
    ll res = n * 5;
    while(x > 0)
    {
        res = min(res, t[x]);
        x -= (x & -x);
    }
    return res;
}

void Enter()
{
     Cin(n);
     fill_n(t, N, 5 * n);
     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 < 5 * n) 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 1912 KB Output is correct
2 Correct 3 ms 1912 KB Output is correct
3 Correct 3 ms 1944 KB Output is correct
4 Correct 3 ms 1944 KB Output is correct
5 Correct 4 ms 2000 KB Output is correct
6 Correct 3 ms 2020 KB Output is correct
7 Correct 3 ms 2020 KB Output is correct
8 Correct 3 ms 2020 KB Output is correct
9 Correct 3 ms 2148 KB Output is correct
10 Correct 3 ms 2164 KB Output is correct
11 Correct 3 ms 2164 KB Output is correct
12 Correct 3 ms 2164 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2164 KB Output is correct
2 Correct 3 ms 2172 KB Output is correct
3 Correct 4 ms 2172 KB Output is correct
4 Correct 5 ms 2172 KB Output is correct
5 Correct 4 ms 2196 KB Output is correct
6 Correct 4 ms 2300 KB Output is correct
7 Correct 4 ms 2300 KB Output is correct
8 Correct 3 ms 2300 KB Output is correct
9 Correct 4 ms 2300 KB Output is correct
10 Correct 4 ms 2304 KB Output is correct
11 Correct 5 ms 2472 KB Output is correct
12 Correct 6 ms 2556 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2556 KB Output is correct
2 Correct 7 ms 2812 KB Output is correct
3 Correct 8 ms 2812 KB Output is correct
4 Correct 26 ms 4212 KB Output is correct
5 Correct 35 ms 4496 KB Output is correct
6 Correct 57 ms 6252 KB Output is correct
7 Correct 45 ms 6252 KB Output is correct
8 Correct 47 ms 6252 KB Output is correct
9 Correct 46 ms 6252 KB Output is correct
10 Correct 54 ms 6256 KB Output is correct
11 Correct 55 ms 6256 KB Output is correct
12 Correct 52 ms 6256 KB Output is correct