oj.uz

Submission #722630

# Submission time Handle Problem Language Result Execution time Memory
722630 2023-04-12T13:08:27 Z fatemetmhr Ants and Sugar (JOI22_sugar) C++17
6 / 100
 4000 ms 826500 KB 
// ~ Be Name Khoda ~

#include <bits/stdc++.h>
//#pragma GCC optimize ("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,O3")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  5e5   + 10;
const int maxn5 =  5e5   + 10;
const int maxnt =  2e6   + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const int lg    =  19;
const ll  inf   =  1e18;

int lim, m, lef[maxn5], rig[maxn5], a[maxn5], ty[maxn5];
int segl[maxnt][2][2], segr[maxnt][2][2], x[maxn5];
ll dp[maxnt][2][2];
vector <int> av;

struct segmnt_tree{

    struct node{
        ll mx[2], lazy[2];
        int id[2];
        node(){
            lazy[0] = lazy[1] = mx[0] = mx[1] = 0;
        }
    } seg[maxn5 << 1];

    int newnode = 2, chil[maxn5 << 1];


    void build(int l, int r, int v){
        seg[v].id[0] = seg[v].id[1] = l;
        if(r - l == 1)
            return;
        int mid = (l + r) >> 1;
        chil[v] = newnode;
        newnode += 2;
        build(l, mid, chil[v]);
        build(mid, r, chil[v] + 1);
    }

    void add(int l, int r, int lq, int rq, int val, int ty, int v){
        if(rq <= l || r <= lq)
            return;
        if(lq <= l && r <= rq){
            seg[v].lazy[ty] += val;
            seg[v].mx[ty] += val;
            return;
        }
        int mid = (l + r) >> 1;
        add(l, mid, lq, rq, val, ty, chil[v]);
        add(mid, r, lq, rq, val, ty, chil[v] + 1);
        int good = chil[v] + (seg[chil[v]].mx[ty] < seg[chil[v] + 1].mx[ty]);
        seg[v].mx[ty] = seg[good].mx[ty] + seg[v].lazy[ty];
        seg[v].id[ty] = seg[good].id[ty];
    }

    pair <ll, int> get_max(int l, int r, int lq, int rq, int ty, int v){
        if(rq <= l || r <= lq)
            return {-inf, 0};
        if(lq <= l && r <= rq)
            return {seg[v].mx[ty], seg[v].id[ty]};
        int mid = (l + r) >> 1;
        auto ans = max(get_max(l, mid, lq, rq, ty, chil[v]), get_max(mid, r, lq, rq, ty, chil[v] + 1));
        return {ans.fi + seg[v].lazy[ty], ans.se};
    }


} seg[lg];

void add(int l, int r, int id, int val, int ty, int v, int h){
    if(r - l == 1){
        dp[v][ty][ty] += val;
        return;
    }
    int mid = (l + r) >> 1;
    if(id < mid){
        add(l, mid, id, val, ty, v * 2, h + 1);
        seg[h].add(0, m, l, id, -val, ty, 1);
    }
    else{
        add(mid, r, id, val, ty, v * 2 + 1, h + 1);
        seg[h].add(0, m, lef[id], mid, -val, ty ^ 1, 1);
    }
    for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++){
        ll val1 = dp[v * 2][i][0] + dp[v * 2 + 1][0][j], val2 = dp[v * 2][i][1] + dp[v * 2 + 1][1][j];
        ll val3 = -inf, val4 = -inf;
        int ind1, ind2;
        if(rig[segr[v * 2][i][0]] < segl[v * 2 + 1][1][j]){
            auto ans = seg[h].get_max(0, m, segr[v * 2][i][0], min(mid, lef[segl[v * 2 + 1][1][j]]), 0, 1);
            val3 = dp[v * 2][i][0] + dp[v * 2 + 1][1][j] + ans.fi;
            ind1 = ans.se;
        }
        if(rig[segr[v * 2][i][1]] < segl[v * 2 + 1][0][j]){
            auto ans = seg[h].get_max(0, m, segr[v * 2][i][1], min(mid, lef[segl[v * 2 + 1][0][j]]), 1, 1);
            val4 = dp[v * 2][i][1] + dp[v * 2 + 1][0][j] + ans.fi;
            //cout << "hmm " << ans.fi << ' ' << ans.se << '\n';
            ind2 = ans.se;
        }
        dp[v][i][j] = max({val1, val2, val3, val4});
        if(val1 >= max({val2, val3, val4})){
            segl[v][i][j] = segl[v * 2][i][0];
            segr[v][i][j] = segr[v * 2 + 1][0][j];
            if(segl[v * 2][i][0] == mid - 1)
                segl[v][i][j] = segl[v * 2 + 1][0][j];
            if(segr[v * 2 + 1][0][j] == mid)
                segr[v][i][j] = segr[v * 2][i][0];
        }
        else if(val2 >= max(val3, val4)){
            segl[v][i][j] = segl[v * 2][i][1];
            segr[v][i][j] = segr[v * 2 + 1][1][j];
            if(segl[v * 2][i][1] == mid - 1)
                segl[v][i][j] = segl[v * 2 + 1][1][j];
            if(segr[v * 2 + 1][1][j] == mid)
                segr[v][i][j] = segr[v * 2][i][1];
        }
        else if(val3 > val4){
            segl[v][i][j] = segl[v * 2][i][0];
            segr[v][i][j] = segr[v * 2 + 1][1][j];
            if(segl[v * 2][i][0] == mid - 1)
                segl[v][i][j] = ind1;
            if(segr[v * 2 + 1][1][j] == mid)
                segr[v][i][j] = rig[ind1] + 1;
        }
        else{
            segl[v][i][j] = segl[v * 2][i][1];
            segr[v][i][j] = segr[v * 2 + 1][0][j];
            if(segl[v * 2][i][1] == mid - 1)
                segl[v][i][j] = ind2;
            if(segr[v * 2 + 1][0][j] == mid)
                segr[v][i][j] = rig[ind2] + 1;
        }
        /*
        cout << "well done " << l << ' ' << r << ' ' << id << ' ' << v << ' ' << i << ' ' << j << ' ' << dp[v][i][j];
        cout << ' ' << val1 << ' ' << val2 << ' ' << val3 << ' ' << val4 << '\n';
        cout << segl[v][i][j] << ' ' << segr[v][i][j] << '\n';
        //*/
    }

    return;
}

void build(int l, int r, int v){
    segl[v][0][0] = segl[v][1][1] = r - 1;
    segr[v][0][0] = segr[v][1][1] = l;
    dp[v][0][1] = dp[v][1][0] = -inf;
    if(r - l == 1)
        return;
    int mid = (l + r) >> 1;
    build(l, mid, v * 2);
    build(mid, r, v * 2 + 1);
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);

    int n; cin >> n >> lim;
    for(int i = 0; i < n; i++){
        cin >> ty[i] >> x[i] >> a[i];
        ty[i]--;
        av.pb(x[i]);
    }
    sort(all(av));
    av.resize(unique(all(av)) - av.begin());
    m = av.size();
    for(int i = 0; i < lg; i++)
        seg[i].build(0, m, 1);
    build(0, m, 1);
    for(int i = 0; i < m; i++){
        lef[i] = lower_bound(all(av), av[i] - lim) - av.begin();
        rig[i] = upper_bound(all(av), av[i] + lim) - av.begin() - 1;
    }
    ll sum = 0;
    for(int i = 0; i < n; i++){
        sum += a[i];
        int pt = lower_bound(all(av), x[i]) - av.begin();
        add(0, m, pt, a[i], ty[i], 1, 0);
        cout << sum - max({dp[1][0][0], dp[1][1][0], dp[1][1][1], dp[1][0][1]}) << '\n';
    }
}

/*
6 6
2 27 12
2 9 11
1 36 10
2 39 4
2 14 9
2 33 7
2 38 20
2 0 20
2 25 16
1 14 3
1 13 19
2 6 4
2 15 6
2 33 4
1 12 11
1 44 1
2 17 14
2 12 19
1 48 18
2 30 16
*/

Compilation message

sugar.cpp: In function 'void add(int, int, int, int, int, int, int)':
sugar.cpp:144:41: warning: 'ind2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  144 |                 segr[v][i][j] = rig[ind2] + 1;
      |                                 ~~~~~~~~^
sugar.cpp:136:41: warning: 'ind1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  136 |                 segr[v][i][j] = rig[ind1] + 1;
      |                                 ~~~~~~~~^

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 744128 KB Output is correct
2 Correct 274 ms 744084 KB Output is correct
3 Correct 286 ms 744136 KB Output is correct
4 Correct 276 ms 744140 KB Output is correct
5 Correct 292 ms 744272 KB Output is correct
6 Correct 318 ms 744728 KB Output is correct
7 Correct 299 ms 744624 KB Output is correct
8 Correct 291 ms 744416 KB Output is correct
9 Correct 303 ms 744396 KB Output is correct
10 Correct 321 ms 745156 KB Output is correct
11 Correct 318 ms 745300 KB Output is correct
12 Correct 312 ms 745428 KB Output is correct
13 Correct 323 ms 745172 KB Output is correct
14 Correct 317 ms 745228 KB Output is correct
15 Correct 324 ms 745220 KB Output is correct
16 Correct 320 ms 745304 KB Output is correct
17 Correct 313 ms 745192 KB Output is correct
18 Correct 318 ms 745188 KB Output is correct
19 Correct 312 ms 745292 KB Output is correct
20 Correct 308 ms 745168 KB Output is correct
21 Correct 323 ms 745232 KB Output is correct
22 Correct 314 ms 745156 KB Output is correct
23 Correct 311 ms 745380 KB Output is correct
24 Correct 320 ms 745216 KB Output is correct
25 Correct 292 ms 745244 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 744168 KB Output is correct
2 Correct 274 ms 744108 KB Output is correct
3 Correct 281 ms 744112 KB Output is correct
4 Execution timed out 4100 ms 826500 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 744140 KB Output is correct
2 Execution timed out 4099 ms 820448 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 744128 KB Output is correct
2 Correct 274 ms 744084 KB Output is correct
3 Correct 286 ms 744136 KB Output is correct
4 Correct 276 ms 744140 KB Output is correct
5 Correct 292 ms 744272 KB Output is correct
6 Correct 318 ms 744728 KB Output is correct
7 Correct 299 ms 744624 KB Output is correct
8 Correct 291 ms 744416 KB Output is correct
9 Correct 303 ms 744396 KB Output is correct
10 Correct 321 ms 745156 KB Output is correct
11 Correct 318 ms 745300 KB Output is correct
12 Correct 312 ms 745428 KB Output is correct
13 Correct 323 ms 745172 KB Output is correct
14 Correct 317 ms 745228 KB Output is correct
15 Correct 324 ms 745220 KB Output is correct
16 Correct 320 ms 745304 KB Output is correct
17 Correct 313 ms 745192 KB Output is correct
18 Correct 318 ms 745188 KB Output is correct
19 Correct 312 ms 745292 KB Output is correct
20 Correct 308 ms 745168 KB Output is correct
21 Correct 323 ms 745232 KB Output is correct
22 Correct 314 ms 745156 KB Output is correct
23 Correct 311 ms 745380 KB Output is correct
24 Correct 320 ms 745216 KB Output is correct
25 Correct 292 ms 745244 KB Output is correct
26 Correct 288 ms 744168 KB Output is correct
27 Correct 274 ms 744108 KB Output is correct
28 Correct 281 ms 744112 KB Output is correct
29 Execution timed out 4100 ms 826500 KB Time limit exceeded
30 Halted 0 ms 0 KB -