oj.uz

Submission #86756

# Submission time Handle Problem Language Result Execution time Memory
86756 2018-11-27T09:27:00 Z karma Divide and conquer (IZhO14_divide) C++11
17 / 100
 5 ms 992 KB 
#include<bits/stdc++.h>
#define For(i, a, b)  for(int i = a; i <= b; ++i)
#define Ford(i, a, b) for(int i = a; i >= b; --i)
#define Task          "test"
#define ld            long double
#define ll            long long
#define X             first
#define Y             second
#define pb            push_back
//#define Karma

using namespace std;

template <typename T> inline void Cin(T &x)
{
    char c;
    x = 0;
    for (c = getchar(); c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

const int N = 2e5 + 7;
const int M = 1e5 + 7;

ll x[M], g[M], r[M], res;
int t[N], n, Maxv;
vector<ll> v;

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(i, 1, n)
     {
         Cin(x[i]), Cin(g[i]), Cin(r[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(i, 1, n)
     {
         res = max(res, g[i] - g[i - 1]);
         int p = lower_bound(v.begin(), v.end(), r[i] - x[i]) - v.begin() + 1;
         int j = Query(p);
         if(j < Maxv) res = max(res, g[i] - g[j - 1]);
         p = lower_bound(v.begin(), v.end(), r[i - 1] - x[i]) - v.begin() + 1;
         Update(p, 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 476 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 2 ms 628 KB Output is correct
6 Correct 2 ms 628 KB Output is correct
7 Correct 2 ms 628 KB Output is correct
8 Correct 2 ms 628 KB Output is correct
9 Correct 2 ms 628 KB Output is correct
10 Correct 2 ms 628 KB Output is correct
11 Correct 2 ms 728 KB Output is correct
12 Correct 2 ms 728 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 992 KB Output isn't correct
2 Halted 0 ms 0 KB -