oj.uz

Submission #847058

# Submission time Handle Problem Language Result Execution time Memory
847058 2023-09-09T05:26:58 Z eltu0815 Ants and Sugar (JOI22_sugar) C++14
42 / 100
 1443 ms 145780 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, sum = 0;
    ll dp[2][2];
    ll lz1, lz2;
    Node() {
        v = sum = 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; ret.sum = l.sum + r.sum;
    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]));
        
        // dp[0][0] of leaf nodes means INF - (lazy updates of lz1), which indicates the number of sugar in the i-th coordinate
        // we have to merge sets that satisfy |S| > 0, but we can also merge the set |S| == 0 and the set |S| > 0 together
        // note that the set whose |S| is 0 always 
        // when there's no ant in the left node, we can make dp[1][i] = -(the number of sugar) + r.dp[1][i] = -l.dp[0][0] + INF + r.dp[1][i];
        if(i == 1 && l.dp[0][0] <= -INF) ret.dp[i][j] = max(ret.dp[i][j], l.sum + r.dp[1][j] + l.v);
        if(j == 1 && r.dp[0][0] <= -INF) ret.dp[i][j] = max(ret.dp[i][j], l.dp[i][1] + r.sum + l.v);
        
        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) {
        seg[node].sum += 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 > idx || ed < idx) return;
    if(str == ed) {
        seg[node].dp[1][1] += val;
        return;
    }
    int mid = str + ed >> 1;
    update3(str, mid, idx, val, node << 1);
    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] <<
          ' ' << seg[node].lz1 << ' ' << seg[node].lz2 << 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;
    for(int i = 1; i <= q; ++i) cin >> query[i].first >> query[i].second.first >> query[i].second.second;
    //for(int i = 1; i <= q; ++i) query[i].first = (i + 1) % 2 + 1, query[i].second.first = rand(), query[i].second.second = rand() + 1;
    //random_shuffle(query + 1, query + q + 1);
    
    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, B = 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);
        }
        else {
            int l = lower_bound(tmp.begin(), tmp.end(), query[i].second.first - L) - tmp.begin();
            int r = upper_bound(tmp.begin(), tmp.end(), query[i].second.first + L) - 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;
            B += query[i].second.second;
            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 << B << ' ';
        cout << A - max_query(0, n, 1) << '\n';
//        if(i == 10) print(0, n, 1);
    }
    return 0;
}

Compilation message

sugar.cpp: In function 'void init(int, int, int)':
sugar.cpp:52:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
sugar.cpp: In function 'void update1(int, int, int, int, ll, int)':
sugar.cpp:87:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
sugar.cpp: In function 'void update2(int, int, int, int, ll, int)':
sugar.cpp:101:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  101 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
sugar.cpp: In function 'void update3(int, int, int, ll, int)':
sugar.cpp:114:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  114 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
sugar.cpp: In function 'void print(int, int, int)':
sugar.cpp:130:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  130 |     int mid = str + ed >> 1;
      |               ~~~~^~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 125784 KB Output is correct
2 Correct 18 ms 125784 KB Output is correct
3 Correct 17 ms 125784 KB Output is correct
4 Correct 17 ms 125784 KB Output is correct
5 Correct 17 ms 125784 KB Output is correct
6 Correct 19 ms 125784 KB Output is correct
7 Incorrect 21 ms 125652 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 125776 KB Output is correct
2 Correct 17 ms 125784 KB Output is correct
3 Correct 17 ms 125788 KB Output is correct
4 Correct 592 ms 141040 KB Output is correct
5 Correct 385 ms 136748 KB Output is correct
6 Correct 689 ms 142632 KB Output is correct
7 Correct 388 ms 136400 KB Output is correct
8 Correct 823 ms 144840 KB Output is correct
9 Correct 800 ms 145616 KB Output is correct
10 Correct 808 ms 145024 KB Output is correct
11 Correct 804 ms 145780 KB Output is correct
12 Correct 345 ms 134324 KB Output is correct
13 Correct 489 ms 136480 KB Output is correct
14 Correct 792 ms 142616 KB Output is correct
15 Correct 832 ms 142296 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 125784 KB Output is correct
2 Correct 344 ms 134764 KB Output is correct
3 Correct 472 ms 136248 KB Output is correct
4 Correct 789 ms 142396 KB Output is correct
5 Correct 781 ms 142276 KB Output is correct
6 Correct 573 ms 140164 KB Output is correct
7 Correct 42 ms 128132 KB Output is correct
8 Correct 286 ms 133976 KB Output is correct
9 Correct 526 ms 136256 KB Output is correct
10 Correct 791 ms 142880 KB Output is correct
11 Correct 949 ms 142796 KB Output is correct
12 Correct 836 ms 142744 KB Output is correct
13 Correct 729 ms 142800 KB Output is correct
14 Correct 858 ms 142892 KB Output is correct
15 Correct 552 ms 142660 KB Output is correct
16 Correct 737 ms 142876 KB Output is correct
17 Correct 1151 ms 142960 KB Output is correct
18 Correct 1276 ms 142820 KB Output is correct
19 Correct 1237 ms 143196 KB Output is correct
20 Correct 1283 ms 143304 KB Output is correct
21 Correct 1377 ms 142924 KB Output is correct
22 Correct 1443 ms 143064 KB Output is correct
23 Correct 1398 ms 142780 KB Output is correct
24 Correct 1273 ms 142752 KB Output is correct
25 Correct 1389 ms 142724 KB Output is correct

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 125784 KB Output is correct
2 Correct 18 ms 125784 KB Output is correct
3 Correct 17 ms 125784 KB Output is correct
4 Correct 17 ms 125784 KB Output is correct
5 Correct 17 ms 125784 KB Output is correct
6 Correct 19 ms 125784 KB Output is correct
7 Incorrect 21 ms 125652 KB Output isn't correct
8 Halted 0 ms 0 KB -