oj.uz

Submission #90063

# Submission time Handle Problem Language Result Execution time Memory
90063 2018-12-20T06:08:44 Z inom Divide and conquer (IZhO14_divide) C++14
100 / 100
 89 ms 25020 KB 
#include<bits/stdc++.h>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>

#define fi first
#define se second
#define new new228
#define pb push_back
#define rank rank228
#define int long long
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
 
using namespace std;
using namespace __gnu_pbds;
 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("fast-math")
#pragma warning(disable : 4996)
 
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; // st.oreder_of_key();

const int N = 100100;
const int INF = 1e15;
const int MAXN = 4 * N;
const int MOD = 998244353;
 
int TN = 1;

int n;
int x[N], g[N], d[N];
int preg[N], pred[N];
int a[N], b[N], t[4 * N];
vector<int> verr;

void update(int v, int tl, int tr, int pos, int val) {
    if (tl == tr) {
        t[v] = min(t[v], val);
        return;
    }
    int tm = (tl + tr) >> 1;
    if (pos <= tm) {
        update(v << 1, tl, tm, pos, val);
    } else {
        update(v << 1 | 1, tm + 1, tr, pos, val);
    }
    t[v] = min(t[v << 1], t[v << 1 | 1]);
}

int get(int v, int tl, int tr, int l, int r) {
    if (tl > r || tr < l) {
        return INF;
    }
    if (tl == l && tr == r) {
        return t[v];
    }
    int tm = (tl + tr) >> 1;
    return min(get(v << 1, tl, tm, l, min(tm, r)), get(v << 1 | 1, tm + 1, tr, max(tm + 1, l), r));
}

void solve() {
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld %lld %lld", &x[i], &g[i], &d[i]);
        d[i] += d[i - 1]; g[i] += g[i - 1];
        verr.pb(x[i] - d[i - 1]);
    }
    sort(all(verr));
    // verr.erase(unique(all(verr)), verr.end());
    /*
    for (auto i: verr) {
        printf("%lld ", i);
    }
    printf("\n\n");
    */
    memset(t, 0x3f, sizeof(t));
    for (int i = 1; i <= n; i++) {
        int now = x[i] - d[i - 1];
        int cur = lower_bound(all(verr), now) - verr.begin();
        // printf("%lld %lld\n", now, cur);
        update(1, 0, n, cur, i);
    }
    // printf("\n");
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int cur = lower_bound(all(verr), x[i] - d[i]) - verr.begin();
        int p = get(1, 0, n, cur, n);
        // printf("%lld\n", p);
        if (p <= n) {
            ans = max(ans, g[i] - g[p - 1]);
        }
    }
    printf("%lld\n", ans);
    return;
}

signed main() {
    // ios_base::sync_with_stdio(0);
    // in; out;  // cin >> TN;
    while (TN--) { solve(); }
    return 0;
 }

Compilation message

divide.cpp:23:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable : 4996)
 
divide.cpp: In function 'void solve()':
divide.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &n);
     ~~~~~^~~~~~~~~~~~
divide.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld %lld", &x[i], &g[i], &d[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3448 KB Output is correct
2 Correct 4 ms 3584 KB Output is correct
3 Correct 4 ms 3640 KB Output is correct
4 Correct 4 ms 3640 KB Output is correct
5 Correct 4 ms 3640 KB Output is correct
6 Correct 4 ms 3708 KB Output is correct
7 Correct 4 ms 3708 KB Output is correct
8 Correct 4 ms 3708 KB Output is correct
9 Correct 4 ms 3708 KB Output is correct
10 Correct 4 ms 3708 KB Output is correct
11 Correct 4 ms 3708 KB Output is correct
12 Correct 5 ms 3708 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3756 KB Output is correct
2 Correct 5 ms 3756 KB Output is correct
3 Correct 5 ms 3756 KB Output is correct
4 Correct 5 ms 3756 KB Output is correct
5 Correct 5 ms 3864 KB Output is correct
6 Correct 6 ms 3892 KB Output is correct
7 Correct 5 ms 4076 KB Output is correct
8 Correct 5 ms 4076 KB Output is correct
9 Correct 6 ms 4076 KB Output is correct
10 Correct 6 ms 4076 KB Output is correct
11 Correct 8 ms 4336 KB Output is correct
12 Correct 9 ms 4452 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4452 KB Output is correct
2 Correct 11 ms 4892 KB Output is correct
3 Correct 11 ms 5016 KB Output is correct
4 Correct 41 ms 7380 KB Output is correct
5 Correct 44 ms 8688 KB Output is correct
6 Correct 89 ms 13224 KB Output is correct
7 Correct 75 ms 15064 KB Output is correct
8 Correct 75 ms 17020 KB Output is correct
9 Correct 73 ms 18684 KB Output is correct
10 Correct 74 ms 20384 KB Output is correct
11 Correct 82 ms 22660 KB Output is correct
12 Correct 83 ms 25020 KB Output is correct