oj.uz

Submission #459242

# Submission time Handle Problem Language Result Execution time Memory
459242 2021-08-08T11:01:20 Z dxz05 Divide and conquer (IZhO14_divide) C++14
100 / 100
 199 ms 43140 KB 
#pragma GCC optimize("Ofast,O2,O3")
#pragma GCC target("avx2")

#include <bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << "[" << H << "]";
    debug_out(T...);
}

#ifdef dddxxz
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define SZ(s) ((int)s.size())
#define all(x) (x).begin(), (x).end()
#define revall(x) (x).rbegin(), (x).rend()

clock_t startTime;

double getCurrentTime() {
    return (double) (clock() - startTime) / CLOCKS_PER_SEC;
}

#define MP make_pair

typedef long long ll;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const double eps = 0.00001;
const int MOD = 1e9;
const int INF = 1000000101;
const long long LLINF = 1223372000000000555;
const int N = 2e6 + 3e2;
const int M = 2522;

ll x[N], pd[N], pg[N];

ll t[N];

void update(int pos, ll val, int v = 1, int tl = 1, int tr = 3e5){
    if (tl == tr){
        t[v] = min(t[v], val);
        return;
    }

    int tm = (tl + tr) >> 1;
    if (pos <= tm) update(pos, val, v + v, tl, tm); else
        update(pos, val, v + v + 1, tm + 1, tr);

    t[v] = min(t[v + v], t[v + v + 1]);
}

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

void solve(int TC) {
    fill(t, t + N, LLINF);

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++){
        cin >> x[i] >> pg[i] >> pd[i];
        pg[i] += pg[i - 1];
        pd[i] += pd[i - 1];
    }

    set<ll> s;
    for (int i = 1; i <= n; i++){
        s.insert(pd[i - 1] - x[i]);
        s.insert(pd[i] - x[i]);
    }

    map<ll, int> mp;
    for (ll k : s) mp[k] = mp.size() + 1;

    ll ans = 0;
    for (int i = 1; i <= n; i++){
        int pos = mp[pd[i - 1] - x[i]];
        update(pos, pg[i - 1]);

        pos = mp[pd[i] - x[i]];
        ans = max(ans, pg[i] - get(1, pos));
    }

    cout << ans;

}

int main() {
    startTime = clock();
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    bool llololcal = false;
#ifdef dddxxz
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    llololcal = true;
#endif

    int TC = 1;
    //cin >> TC;

    for (int test = 1; test <= TC; test++) {
        debug(test);
        //cout << "Case #" << test << ": ";
        solve(test);
    }

    if (llololcal) cerr << endl << "Time: " << int(getCurrentTime() * 1000) << " ms" << endl;

    return 0;
}

Compilation message

divide.cpp: In function 'int main()':
divide.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
divide.cpp:118:9: note: in expansion of macro 'debug'
  118 |         debug(test);
      |         ^~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15948 KB Output is correct
2 Correct 8 ms 15984 KB Output is correct
3 Correct 8 ms 16004 KB Output is correct
4 Correct 10 ms 15948 KB Output is correct
5 Correct 8 ms 15996 KB Output is correct
6 Correct 8 ms 15948 KB Output is correct
7 Correct 8 ms 15948 KB Output is correct
8 Correct 10 ms 15948 KB Output is correct
9 Correct 8 ms 16024 KB Output is correct
10 Correct 8 ms 15992 KB Output is correct
11 Correct 8 ms 16008 KB Output is correct
12 Correct 8 ms 15948 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15948 KB Output is correct
2 Correct 8 ms 15984 KB Output is correct
3 Correct 8 ms 16004 KB Output is correct
4 Correct 10 ms 15948 KB Output is correct
5 Correct 8 ms 15996 KB Output is correct
6 Correct 8 ms 15948 KB Output is correct
7 Correct 8 ms 15948 KB Output is correct
8 Correct 10 ms 15948 KB Output is correct
9 Correct 8 ms 16024 KB Output is correct
10 Correct 8 ms 15992 KB Output is correct
11 Correct 8 ms 16008 KB Output is correct
12 Correct 8 ms 15948 KB Output is correct
13 Correct 8 ms 15948 KB Output is correct
14 Correct 8 ms 15948 KB Output is correct
15 Correct 9 ms 16092 KB Output is correct
16 Correct 9 ms 16076 KB Output is correct
17 Correct 10 ms 16204 KB Output is correct
18 Correct 10 ms 16332 KB Output is correct
19 Correct 10 ms 16204 KB Output is correct
20 Correct 9 ms 16184 KB Output is correct
21 Correct 10 ms 16384 KB Output is correct
22 Correct 11 ms 16432 KB Output is correct
23 Correct 16 ms 17228 KB Output is correct
24 Correct 16 ms 17404 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15948 KB Output is correct
2 Correct 8 ms 15984 KB Output is correct
3 Correct 8 ms 16004 KB Output is correct
4 Correct 10 ms 15948 KB Output is correct
5 Correct 8 ms 15996 KB Output is correct
6 Correct 8 ms 15948 KB Output is correct
7 Correct 8 ms 15948 KB Output is correct
8 Correct 10 ms 15948 KB Output is correct
9 Correct 8 ms 16024 KB Output is correct
10 Correct 8 ms 15992 KB Output is correct
11 Correct 8 ms 16008 KB Output is correct
12 Correct 8 ms 15948 KB Output is correct
13 Correct 8 ms 15948 KB Output is correct
14 Correct 8 ms 15948 KB Output is correct
15 Correct 9 ms 16092 KB Output is correct
16 Correct 9 ms 16076 KB Output is correct
17 Correct 10 ms 16204 KB Output is correct
18 Correct 10 ms 16332 KB Output is correct
19 Correct 10 ms 16204 KB Output is correct
20 Correct 9 ms 16184 KB Output is correct
21 Correct 10 ms 16384 KB Output is correct
22 Correct 11 ms 16432 KB Output is correct
23 Correct 16 ms 17228 KB Output is correct
24 Correct 16 ms 17404 KB Output is correct
25 Correct 15 ms 17152 KB Output is correct
26 Correct 22 ms 18508 KB Output is correct
27 Correct 24 ms 18592 KB Output is correct
28 Correct 93 ms 29044 KB Output is correct
29 Correct 91 ms 29408 KB Output is correct
30 Correct 199 ms 43140 KB Output is correct
31 Correct 180 ms 42020 KB Output is correct
32 Correct 187 ms 42024 KB Output is correct
33 Correct 170 ms 41744 KB Output is correct
34 Correct 186 ms 41088 KB Output is correct
35 Correct 181 ms 42396 KB Output is correct
36 Correct 177 ms 42556 KB Output is correct