Submission #847067

#	Time	Username	Problem	Language	Result	Execution time	Memory
847067		eltu0815	Ants and Sugar (JOI22_sugar)	C++14	100 / 100	1542 ms	142064 KiB

sugar

#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;
    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 + l.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]));
        
        // 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 has a negative or zero contribution
        // so when we merge with the set whose |S| is 0, it's always optimal to contribute -(lazy updates of lz1),
        // so that it can be combined with l[i][1] and r[1][j].
        
        // 한국어로 다시 쓰자면, 아무런 개미가 선택되지 않은 셋은 항상 음수 또는 0의 기여도를 가지는데,
        // 이들이 양옆에 있는 노드의 1과 결합하면 양수의 기여도를 가지게 할 수 있음
        // 따라서 아무런 개미가 선택되지 않은 노드는 그 노드의 x 전체를 1로 만들어 merge하는 경우까지 추가로 고려해야 하며,
        // 그 노드 x 전체를 1로 만들면 기여도는 그 구간에서 발생한 lz1 업데이트의 총합임
        if(i == 1) ret.dp[i][j] = max(ret.dp[i][j], l.sum + r.dp[1][j] + l.v);
        if(j == 1) 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, seg[1].dp[0][0]);
}

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;
    
    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;
            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 << A - max_query(0, n, 1) << '\n';
    }
    return 0;
}

Compilation message (stderr)

sugar.cpp: In function 'void init(int, int, int)':
sugar.cpp:57:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
sugar.cpp: In function 'void update1(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 update2(int, int, int, int, ll, int)':
sugar.cpp:106:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  106 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
sugar.cpp: In function 'void update3(int, int, int, ll, int)':
sugar.cpp:119:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  119 |     int mid = str + ed >> 1;
      |               ~~~~^~~~

• Subtask 1: 6 / 6
• Subtask 2: 16 / 16
• Subtask 3: 26 / 26
• Subtask 4: 52 / 52