oj.uz

Submission #86772

# Submission time Handle Problem Language Result Execution time Memory
86772 2018-11-27T11:18:54 Z karma Divide and conquer (IZhO14_divide) C++14
100 / 100
 49 ms 4264 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 = 1e5 + 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 = n + 5;
    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]);
    }
    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;
 
    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 376 KB Output is correct
3 Correct 2 ms 412 KB Output is correct
4 Correct 2 ms 580 KB Output is correct
5 Correct 2 ms 580 KB Output is correct
6 Correct 2 ms 580 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 2 ms 632 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 2 ms 632 KB Output is correct
12 Correct 2 ms 632 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 2 ms 636 KB Output is correct
5 Correct 2 ms 636 KB Output is correct
6 Correct 2 ms 636 KB Output is correct
7 Correct 3 ms 636 KB Output is correct
8 Correct 2 ms 636 KB Output is correct
9 Correct 2 ms 636 KB Output is correct
10 Correct 3 ms 660 KB Output is correct
11 Correct 4 ms 892 KB Output is correct
12 Correct 4 ms 892 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 892 KB Output is correct
2 Correct 5 ms 1064 KB Output is correct
3 Correct 6 ms 1064 KB Output is correct
4 Correct 22 ms 2548 KB Output is correct
5 Correct 24 ms 2552 KB Output is correct
6 Correct 49 ms 4264 KB Output is correct
7 Correct 42 ms 4264 KB Output is correct
8 Correct 41 ms 4264 KB Output is correct
9 Correct 45 ms 4264 KB Output is correct
10 Correct 46 ms 4264 KB Output is correct
11 Correct 42 ms 4264 KB Output is correct
12 Correct 45 ms 4264 KB Output is correct