oj.uz

Submission #86771

# Submission time Handle Problem Language Result Execution time Memory
86771 2018-11-27T11:18:07 Z karma Divide and conquer (IZhO14_divide) C++11
100 / 100
 48 ms 4212 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 508 KB Output is correct
3 Correct 2 ms 508 KB Output is correct
4 Correct 2 ms 584 KB Output is correct
5 Correct 2 ms 584 KB Output is correct
6 Correct 2 ms 584 KB Output is correct
7 Correct 2 ms 584 KB Output is correct
8 Correct 2 ms 584 KB Output is correct
9 Correct 2 ms 584 KB Output is correct
10 Correct 2 ms 584 KB Output is correct
11 Correct 2 ms 584 KB Output is correct
12 Correct 2 ms 584 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 584 KB Output is correct
2 Correct 2 ms 584 KB Output is correct
3 Correct 2 ms 584 KB Output is correct
4 Correct 2 ms 584 KB Output is correct
5 Correct 2 ms 584 KB Output is correct
6 Correct 3 ms 584 KB Output is correct
7 Correct 2 ms 584 KB Output is correct
8 Correct 2 ms 584 KB Output is correct
9 Correct 2 ms 584 KB Output is correct
10 Correct 3 ms 688 KB Output is correct
11 Correct 4 ms 832 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 1148 KB Output is correct
3 Correct 5 ms 1148 KB Output is correct
4 Correct 23 ms 2552 KB Output is correct
5 Correct 24 ms 2552 KB Output is correct
6 Correct 48 ms 4208 KB Output is correct
7 Correct 38 ms 4212 KB Output is correct
8 Correct 39 ms 4212 KB Output is correct
9 Correct 38 ms 4212 KB Output is correct
10 Correct 38 ms 4212 KB Output is correct
11 Correct 42 ms 4212 KB Output is correct
12 Correct 47 ms 4212 KB Output is correct