oj.uz

Submission #86758

# Submission time Handle Problem Language Result Execution time Memory
86758 2018-11-27T09:35:54 Z karma Divide and conquer (IZhO14_divide) C++11
100 / 100
 78 ms 5484 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)
{
    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;

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 380 KB Output is correct
3 Correct 2 ms 440 KB Output is correct
4 Correct 2 ms 440 KB Output is correct
5 Correct 2 ms 456 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 564 KB Output is correct
8 Correct 2 ms 564 KB Output is correct
9 Correct 2 ms 644 KB Output is correct
10 Correct 2 ms 644 KB Output is correct
11 Correct 2 ms 644 KB Output is correct
12 Correct 2 ms 644 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 644 KB Output is correct
2 Correct 2 ms 644 KB Output is correct
3 Correct 2 ms 644 KB Output is correct
4 Correct 9 ms 644 KB Output is correct
5 Correct 3 ms 652 KB Output is correct
6 Correct 3 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 3 ms 736 KB Output is correct
10 Correct 3 ms 736 KB Output is correct
11 Correct 5 ms 1004 KB Output is correct
12 Correct 5 ms 1004 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1004 KB Output is correct
2 Correct 6 ms 1260 KB Output is correct
3 Correct 7 ms 1260 KB Output is correct
4 Correct 26 ms 3044 KB Output is correct
5 Correct 29 ms 3172 KB Output is correct
6 Correct 54 ms 5484 KB Output is correct
7 Correct 47 ms 5484 KB Output is correct
8 Correct 49 ms 5484 KB Output is correct
9 Correct 46 ms 5484 KB Output is correct
10 Correct 48 ms 5484 KB Output is correct
11 Correct 50 ms 5484 KB Output is correct
12 Correct 78 ms 5484 KB Output is correct