oj.uz

Submission #722631

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

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

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;
      |                                 ~~~~~~~~^
sugar.cpp: In function 'int main()':
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:101:19: note: 'ind2' was declared here
  101 |         int ind1, ind2;
      |                   ^~~~
sugar.cpp:136:41: warning: 'ind1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  136 |                 segr[v][i][j] = rig[ind1] + 1;
      |                                 ~~~~~~~~^
sugar.cpp:101:13: note: 'ind1' was declared here
  101 |         int ind1, ind2;
      |             ^~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 744216 KB Output is correct
2 Correct 322 ms 744120 KB Output is correct
3 Correct 334 ms 744068 KB Output is correct
4 Correct 357 ms 744144 KB Output is correct
5 Correct 336 ms 744168 KB Output is correct
6 Correct 352 ms 744628 KB Output is correct
7 Correct 375 ms 744684 KB Output is correct
8 Correct 363 ms 744452 KB Output is correct
9 Correct 376 ms 744344 KB Output is correct
10 Correct 397 ms 745328 KB Output is correct
11 Correct 404 ms 745212 KB Output is correct
12 Correct 402 ms 745268 KB Output is correct
13 Correct 375 ms 745352 KB Output is correct
14 Correct 417 ms 745228 KB Output is correct
15 Correct 375 ms 745212 KB Output is correct
16 Correct 413 ms 745240 KB Output is correct
17 Correct 369 ms 745316 KB Output is correct
18 Correct 357 ms 745228 KB Output is correct
19 Correct 384 ms 745232 KB Output is correct
20 Correct 356 ms 745224 KB Output is correct
21 Correct 357 ms 745268 KB Output is correct
22 Correct 357 ms 745128 KB Output is correct
23 Correct 342 ms 745244 KB Output is correct
24 Correct 346 ms 745232 KB Output is correct
25 Correct 321 ms 745228 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 744092 KB Output is correct
2 Correct 306 ms 744172 KB Output is correct
3 Correct 337 ms 744052 KB Output is correct
4 Execution timed out 4080 ms 819732 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 744060 KB Output is correct
2 Execution timed out 4102 ms 815884 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 744216 KB Output is correct
2 Correct 322 ms 744120 KB Output is correct
3 Correct 334 ms 744068 KB Output is correct
4 Correct 357 ms 744144 KB Output is correct
5 Correct 336 ms 744168 KB Output is correct
6 Correct 352 ms 744628 KB Output is correct
7 Correct 375 ms 744684 KB Output is correct
8 Correct 363 ms 744452 KB Output is correct
9 Correct 376 ms 744344 KB Output is correct
10 Correct 397 ms 745328 KB Output is correct
11 Correct 404 ms 745212 KB Output is correct
12 Correct 402 ms 745268 KB Output is correct
13 Correct 375 ms 745352 KB Output is correct
14 Correct 417 ms 745228 KB Output is correct
15 Correct 375 ms 745212 KB Output is correct
16 Correct 413 ms 745240 KB Output is correct
17 Correct 369 ms 745316 KB Output is correct
18 Correct 357 ms 745228 KB Output is correct
19 Correct 384 ms 745232 KB Output is correct
20 Correct 356 ms 745224 KB Output is correct
21 Correct 357 ms 745268 KB Output is correct
22 Correct 357 ms 745128 KB Output is correct
23 Correct 342 ms 745244 KB Output is correct
24 Correct 346 ms 745232 KB Output is correct
25 Correct 321 ms 745228 KB Output is correct
26 Correct 333 ms 744092 KB Output is correct
27 Correct 306 ms 744172 KB Output is correct
28 Correct 337 ms 744052 KB Output is correct
29 Execution timed out 4080 ms 819732 KB Time limit exceeded
30 Halted 0 ms 0 KB -