oj.uz

Submission #86762

# Submission time Handle Problem Language Result Execution time Memory
86762 2018-11-27T09:43:19 Z karma Divide and conquer (IZhO14_divide) C++11
100 / 100
 62 ms 5488 KB 
#include<bits/stdc++.h>
#define ll            long long
#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;
int t[N], n, Maxv;
vector<ll> v;

inline void Minimize(int& x, int y) {if(x < y) x = y;}
inline void Update(int x, int val)
{
    while(x <= Maxv)
    {
        t[x] = min(t[x], val);
        x += (x & -x);
    }
}
inline int Query(int x)
{
    int res = Maxv;
    while(x > 0)
    {
        res = min(res, t[x]);
        x -= (x & -x);
    }
    return 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

    Cin(n);
    Maxv = 2 * n + 2;
    fill_n(t, Maxv + 2, Maxv);
    for(int i = 1; i <= n; ++i)
    {
        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());
    for(int i = 1; i <= n; ++i)
    {
        int 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]);
        Update(lower_bound(v.begin(), v.end(), r[i - 1] - x[i]) - v.begin() + 1, i);
    }
    cout << res;

    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 508 KB Output is correct
3 Correct 2 ms 508 KB Output is correct
4 Correct 2 ms 508 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 2 ms 508 KB Output is correct
7 Correct 2 ms 508 KB Output is correct
8 Correct 2 ms 508 KB Output is correct
9 Correct 2 ms 692 KB Output is correct
10 Correct 2 ms 692 KB Output is correct
11 Correct 2 ms 692 KB Output is correct
12 Correct 3 ms 692 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 692 KB Output is correct
2 Correct 2 ms 692 KB Output is correct
3 Correct 2 ms 692 KB Output is correct
4 Correct 2 ms 692 KB Output is correct
5 Correct 3 ms 692 KB Output is correct
6 Correct 3 ms 692 KB Output is correct
7 Correct 3 ms 692 KB Output is correct
8 Correct 2 ms 692 KB Output is correct
9 Correct 3 ms 720 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 4 ms 976 KB Output is correct
12 Correct 4 ms 992 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 992 KB Output is correct
2 Correct 6 ms 1248 KB Output is correct
3 Correct 9 ms 1376 KB Output is correct
4 Correct 29 ms 3040 KB Output is correct
5 Correct 29 ms 3172 KB Output is correct
6 Correct 57 ms 5472 KB Output is correct
7 Correct 45 ms 5484 KB Output is correct
8 Correct 46 ms 5488 KB Output is correct
9 Correct 49 ms 5488 KB Output is correct
10 Correct 51 ms 5488 KB Output is correct
11 Correct 51 ms 5488 KB Output is correct
12 Correct 62 ms 5488 KB Output is correct