Submission #846743

#	Time	Username	Problem	Language	Result	Execution time	Memory
846743		eltu0815	Ants and Sugar (JOI22_sugar)	C++14	26 / 100	511 ms	113340 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;
pii ant[MAX], sugar[MAX];

ll sum[MAX];
ll sugar1[MAX], sugar2[MAX];

struct Node {
    int s, e;
    ll dp[2][2];
    Node() { dp[0][0] = dp[1][0] = dp[0][1] = dp[1][1] = -INF; }
};

Node Merge(Node l, Node r) {
    Node ret = Node();
    ret.s = l.s, ret.e = r.e;
    for(int i = 0; i <= 1; ++i) for(int j = 0; j <= 1; ++j) {
        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) * sugar2[l.e]);
        }
    }
    return ret;
}

Node seg[MAX << 2];
void init(int str, int ed, int node) {
    if(str == ed) {
        seg[node].s = seg[node].e = str;
        seg[node].dp[0][0] = 0;
        seg[node].dp[1][1] = -sugar1[str];
        seg[node].dp[0][1] = seg[node].dp[1][0] = -INF;
        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 update(int str, int ed, int idx, int node) {
    if(str == ed){
        seg[node].dp[1][1] = sum[str] - sugar1[str];
        return;
    }
    int mid = str + ed >> 1;
    if(idx <= mid) update(str, mid, idx, node << 1);
    else update(mid + 1, ed, idx, node << 1 | 1);
    seg[node] = Merge(seg[node << 1], seg[node << 1 | 1]);
}

ll query() {
    return 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) {
    cout << str << ' ' << ed << " : " << 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/2; ++i) cin >> tt >> sugar[i].first >> sugar[i].second;
    for(int i = 1; i <= q/2; ++i) cin >> tt >> ant[i].first >> ant[i].second;
    
    vector<int> tmp;
    for(int i = 1; i <= q/2; ++i) tmp.push_back(ant[i].first);
    sort(tmp.begin(), tmp.end()); tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
    
    for(int i = 1; i <= q/2; ++i) {
        int l = lower_bound(tmp.begin(), tmp.end(), sugar[i].first - L) - tmp.begin() + 1;
        int r = lower_bound(tmp.begin(), tmp.end(), sugar[i].first + L + 1) - tmp.begin();
        if(tmp[r - 1] < sugar[i].first - L) continue;
        if(tmp[l - 1] > sugar[i].first + L) continue;
        sugar1[l] += sugar[i].second, sugar1[r + 1] -= sugar[i].second;
        sugar2[l] += sugar[i].second, sugar2[r] -= sugar[i].second;
    }
    for(int i = 1; i <= q/2 + 1; ++i) sugar1[i] += sugar1[i - 1], sugar2[i] += sugar2[i - 1];
    
    init(0, q/2 + 1, 1); ll A = 0;
    for(int i = 1; i <= q/2; ++i) cout << 0 << '\n';
    for(int i = 1; i <= q/2; ++i) {
        int idx = lower_bound(tmp.begin(), tmp.end(), ant[i].first) - tmp.begin() + 1;
        A += ant[i].second; sum[idx] += ant[i].second;
        update(0, q/2 + 1, idx, 1);
        cout << A - query() << '\n';
    }
    return 0;
}

Compilation message (stderr)

sugar.cpp: In function 'void init(int, int, int)':
sugar.cpp:46:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |     int mid = str + ed >>1;
      |               ~~~~^~~~
sugar.cpp: In function 'void update(int, int, int, int)':
sugar.cpp:57:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
sugar.cpp: In function 'void print(int, int, int)':
sugar.cpp:70:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |     int mid = str + ed >> 1;
      |               ~~~~^~~~

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