oj.uz

Submission #86760

# Submission time Handle Problem Language Result Execution time Memory
86760 2018-11-27T09:41:45 Z karma Divide and conquer (IZhO14_divide) C++11
100 / 100
 70 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;}

void Update(int x, int val)
{
     while(x <= Maxv)
     {
         t[x] = min(t[x], val);
         x += (x & -x);
     }
}

int Query(int x)
{
    int res = Maxv;
    while(x > 0)
    {
        res = min(res, t[x]);
        x -= (x & -x);
    }
    return res;
}

void Enter()
{
     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());
}

void Solve()
{
     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;
}

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 2 ms 376 KB Output is correct
2 Correct 2 ms 440 KB Output is correct
3 Correct 2 ms 440 KB Output is correct
4 Correct 3 ms 444 KB Output is correct
5 Correct 2 ms 544 KB Output is correct
6 Correct 2 ms 580 KB Output is correct
7 Correct 3 ms 580 KB Output is correct
8 Correct 2 ms 580 KB Output is correct
9 Correct 2 ms 580 KB Output is correct
10 Correct 2 ms 580 KB Output is correct
11 Correct 2 ms 656 KB Output is correct
12 Correct 2 ms 656 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 656 KB Output is correct
2 Correct 2 ms 656 KB Output is correct
3 Correct 2 ms 656 KB Output is correct
4 Correct 2 ms 656 KB Output is correct
5 Correct 3 ms 656 KB Output is correct
6 Correct 3 ms 716 KB Output is correct
7 Correct 2 ms 716 KB Output is correct
8 Correct 3 ms 720 KB Output is correct
9 Correct 2 ms 736 KB Output is correct
10 Correct 3 ms 844 KB Output is correct
11 Correct 4 ms 1100 KB Output is correct
12 Correct 5 ms 1100 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1100 KB Output is correct
2 Correct 6 ms 1260 KB Output is correct
3 Correct 6 ms 1260 KB Output is correct
4 Correct 25 ms 3168 KB Output is correct
5 Correct 26 ms 3168 KB Output is correct
6 Correct 56 ms 5484 KB Output is correct
7 Correct 53 ms 5488 KB Output is correct
8 Correct 70 ms 5488 KB Output is correct
9 Correct 47 ms 5488 KB Output is correct
10 Correct 48 ms 5488 KB Output is correct
11 Correct 51 ms 5488 KB Output is correct
12 Correct 52 ms 5488 KB Output is correct