oj.uz

Submission #86817

# Submission time Handle Problem Language Result Execution time Memory
86817 2018-11-27T15:46:37 Z karma Divide and conquer (IZhO14_divide) C++11
100 / 100
 53 ms 4116 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#define pb            push_back

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';
}

long long res;
int n, Maxv;
vector<long long> v, g, r;
vector<int> t, x;

inline void Update(int x, const 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);
    Cin(n);
    Maxv = n + 3;
    t.resize(Maxv, Maxv);
    x.resize(n + 1), g.resize(n + 1), r.resize(n + 1);
    g[0] = r[0] = x[0] = 0;
    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]);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    v.pb(v.back() + 1);
    for(int i = 1; i <= n; ++i)
    {
        int j = Query(upper_bound(v.begin(), v.end(), r[i] - x[i]) - v.begin());
        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;
}

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

Subtask #2
31.0 / 31.0

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

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 764 KB Output is correct
2 Correct 5 ms 1020 KB Output is correct
3 Correct 6 ms 1020 KB Output is correct
4 Correct 23 ms 2428 KB Output is correct
5 Correct 26 ms 2428 KB Output is correct
6 Correct 53 ms 4088 KB Output is correct
7 Correct 42 ms 4116 KB Output is correct
8 Correct 46 ms 4116 KB Output is correct
9 Correct 42 ms 4116 KB Output is correct
10 Correct 42 ms 4116 KB Output is correct
11 Correct 46 ms 4116 KB Output is correct
12 Correct 49 ms 4116 KB Output is correct