oj.uz

Submission #846900

# Submission time Handle Problem Language Result Execution time Memory
846900 2023-09-08T15:48:56 Z eltu0815 Ants and Sugar (JOI22_sugar) C++14
42 / 100
 1381 ms 135808 KB 
#include <bits/stdc++.h>
#define MAX 500005
#define MOD 998244353
#define INF (ll)(1e18)
#define inf (1987654321)

using namespace std;    
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef complex<long double> cpx;
constexpr long double PI = acos(-1);

int q, L;
int chk[MAX];
pair<int, pii> query[MAX];

struct Node {
    ll v;
    ll dp[2][2];
    ll lz1, lz2;
    Node() {
        v = 0;
        dp[0][0] = dp[1][0] = dp[0][1] = dp[1][1] = -INF;
        lz1 = lz2 = 0;
    }
};

Node Merge(Node l, Node r) {
    Node ret = Node(); ret.v = r.v;
    for(int i = 0; i <= 1; ++i) for(int j = 0; j <= 1; ++j) {
        if(i == 0) ret.dp[i][j] = max(ret.dp[i][j], max(r.dp[0][j], r.dp[1][j]));
        if(j == 0) ret.dp[i][j] = max(ret.dp[i][j], max(l.dp[i][0], l.dp[i][1]));
        for(int a = 0; a <= 1; ++a) for(int b = 0; b <= 1; ++b) {
            ret.dp[i][j] = max(ret.dp[i][j], l.dp[i][a] + r.dp[b][j] + (a & b) * l.v);
        }
    }
    return ret;
}

Node seg[MAX << 2];
void init(int str, int ed, int node) {
    if(str == ed) return;
    int mid = str + ed >> 1;
    init(str, mid, node << 1);
    init(mid + 1, ed, node << 1 | 1);
    seg[node] = Merge(seg[node << 1], seg[node << 1 | 1]);
}

void lazyProp(int str, int ed, int node) {
    if(seg[node].lz1) {
        for(int i = 0; i <= 1; ++i) for(int j = 0; j <= 1; ++j) seg[node].dp[i][j] += seg[node].lz1;
        if(str != ed) {
            seg[node << 1].lz1 += seg[node].lz1;
            seg[node << 1 | 1].lz1 += seg[node].lz1;
        }
        seg[node].lz1 = 0;
    }
    
    if(seg[node].lz2) {
        seg[node].v += seg[node].lz2;
        if(str != ed) {
            seg[node << 1].lz2 += seg[node].lz2;
            seg[node << 1 | 1].lz2 += seg[node].lz2;
        }
        seg[node].lz2 = 0;
    }
}

void update1(int str, int ed, int left, int right, ll val, int node) {
    lazyProp(str, ed, node);
    if(str > right || ed < left) return;
    if(left <= str && ed <= right) {
        seg[node].lz1 = val;
        lazyProp(str, ed, node);
        return;
    }
    int mid = str + ed >> 1;
    update1(str, mid, left, right, val, node << 1);
    update1(mid + 1, ed, left, right, val, node << 1 | 1);
    seg[node] = Merge(seg[node << 1], seg[node << 1 | 1]);
}

void update2(int str, int ed, int left, int right, ll val, int node) {
    lazyProp(str, ed, node);
    if(str > right || ed < left) return;
    if(left <= str && ed <= right) {
        seg[node].lz2 = val;
        lazyProp(str, ed, node);
        return;
    }
    int mid = str + ed >> 1;
    update2(str, mid, left, right, val, node << 1);
    update2(mid + 1, ed, left, right, val, node << 1 | 1);
    seg[node] = Merge(seg[node << 1], seg[node << 1 | 1]);
}

void update3(int str, int ed, int idx, ll val, int node) {
    lazyProp(str, ed, node);
    if(str == ed) {
        seg[node].dp[1][1] += val;
        return;
    }
    int mid = str + ed >> 1;
    if(idx <= mid) update3(str, mid, idx, val, node << 1);
    else update3(mid + 1, ed, idx, val, node << 1 | 1);
    seg[node] = Merge(seg[node << 1], seg[node << 1 | 1]);
}

ll max_query(int str, int ed, int node) {
    lazyProp(str, ed, node);
    return max(0ll, max(max(seg[1].dp[0][0], seg[1].dp[1][1]), max(seg[1].dp[0][1], seg[1].dp[1][0])));
}

void print(int str, int ed, int node) {
    lazyProp(str, ed, node);
    cout << str << ' ' << ed << " : " << seg[node].v << ' ' << seg[node].dp[0][0] << ' ' << seg[node].dp[1][0] << ' ' << seg[node].dp[0][1] << ' ' << seg[node].dp[1][1] << endl;
    if(str == ed) return;
    int mid = str + ed >> 1;
    print(str, mid, node << 1);
    print(mid + 1, ed, node << 1 | 1);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> q >> L; int tt;
    for(int i = 1; i <= q; ++i) cin >> query[i].first >> query[i].second.first >> query[i].second.second;
    
    vector<int> tmp; tmp.push_back(-1000000005); tmp.push_back(2000000005);
    for(int i = 1; i <= q; ++i) if(query[i].first == 1) tmp.push_back(query[i].second.first);
    sort(tmp.begin(), tmp.end()); tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
    
    int n = tmp.size() - 1;
    init(0, n, 1); ll A = 0;
    for(int i = 1; i <= q; ++i) {
        if(query[i].first == 1) {
            int idx = lower_bound(tmp.begin(), tmp.end(), query[i].second.first) - tmp.begin();
            A += query[i].second.second;
            if(chk[idx] == 0) chk[idx] = 1, update3(0, n, idx, 1ll * query[i].second.second + INF, 1);
            else update3(0, n, idx, query[i].second.second, 1);
            cout << A - max_query(0, n, 1) << '\n';
        }
        else {
            int l = lower_bound(tmp.begin(), tmp.end(), query[i].second.first - L) - tmp.begin();
            int r = lower_bound(tmp.begin(), tmp.end(), query[i].second.first + L + 1) - tmp.begin() - 1;
            //if(l <= r) cout <<"WOW" << l << ' ' << r << ' ' << query[i].second.first - L << ' ' << query[i].second.first + L << ' ' << tmp[l] << ' ' << tmp[r] << endl;
            if(l <= r) update1(0, n, l, r, -query[i].second.second, 1);
            if(l < r) update2(0, n, l, r - 1, query[i].second.second, 1);
            cout << A - max_query(0, n, 1) << '\n';
        }
        //print(0, n, 1);
    }
    return 0;
}

Compilation message

sugar.cpp: In function 'void init(int, int, int)':
sugar.cpp:44:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
sugar.cpp: In function 'void update1(int, int, int, int, ll, int)':
sugar.cpp:78:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
sugar.cpp: In function 'void update2(int, int, int, int, ll, int)':
sugar.cpp:92:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
sugar.cpp: In function 'void update3(int, int, int, ll, int)':
sugar.cpp:104:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  104 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
sugar.cpp: In function 'void print(int, int, int)':
sugar.cpp:119:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  119 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
sugar.cpp: In function 'int main()':
sugar.cpp:129:24: warning: unused variable 'tt' [-Wunused-variable]
  129 |     cin >> q >> L; int tt;
      |                        ^~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 111192 KB Output is correct
2 Correct 16 ms 111192 KB Output is correct
3 Correct 16 ms 111452 KB Output is correct
4 Correct 16 ms 111448 KB Output is correct
5 Correct 16 ms 111192 KB Output is correct
6 Incorrect 18 ms 111448 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 111448 KB Output is correct
2 Correct 16 ms 111452 KB Output is correct
3 Correct 16 ms 111448 KB Output is correct
4 Correct 533 ms 128552 KB Output is correct
5 Correct 331 ms 122316 KB Output is correct
6 Correct 675 ms 130956 KB Output is correct
7 Correct 342 ms 122572 KB Output is correct
8 Correct 783 ms 135108 KB Output is correct
9 Correct 710 ms 135808 KB Output is correct
10 Correct 798 ms 135092 KB Output is correct
11 Correct 707 ms 135696 KB Output is correct
12 Correct 336 ms 120272 KB Output is correct
13 Correct 430 ms 124960 KB Output is correct
14 Correct 724 ms 132300 KB Output is correct
15 Correct 722 ms 132216 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 111188 KB Output is correct
2 Correct 308 ms 118664 KB Output is correct
3 Correct 428 ms 125128 KB Output is correct
4 Correct 728 ms 132156 KB Output is correct
5 Correct 715 ms 132176 KB Output is correct
6 Correct 585 ms 127652 KB Output is correct
7 Correct 45 ms 111688 KB Output is correct
8 Correct 270 ms 115904 KB Output is correct
9 Correct 500 ms 119304 KB Output is correct
10 Correct 817 ms 123080 KB Output is correct
11 Correct 947 ms 122936 KB Output is correct
12 Correct 798 ms 122828 KB Output is correct
13 Correct 722 ms 122808 KB Output is correct
14 Correct 830 ms 122956 KB Output is correct
15 Correct 511 ms 122908 KB Output is correct
16 Correct 680 ms 122856 KB Output is correct
17 Correct 1064 ms 123080 KB Output is correct
18 Correct 1278 ms 122928 KB Output is correct
19 Correct 1166 ms 122816 KB Output is correct
20 Correct 1220 ms 122832 KB Output is correct
21 Correct 1295 ms 122888 KB Output is correct
22 Correct 1363 ms 122884 KB Output is correct
23 Correct 1381 ms 123272 KB Output is correct
24 Correct 1148 ms 123216 KB Output is correct
25 Correct 1269 ms 122808 KB Output is correct

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 111192 KB Output is correct
2 Correct 16 ms 111192 KB Output is correct
3 Correct 16 ms 111452 KB Output is correct
4 Correct 16 ms 111448 KB Output is correct
5 Correct 16 ms 111192 KB Output is correct
6 Incorrect 18 ms 111448 KB Output isn't correct
7 Halted 0 ms 0 KB -