oj.uz

Submission #846743

# Submission time Handle Problem Language Result Execution time Memory
846743 2023-09-08T11:00:59 Z eltu0815 Ants and Sugar (JOI22_sugar) C++14
26 / 100
 511 ms 113340 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;
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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 88920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 88664 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 88664 KB Output is correct
2 Correct 125 ms 99536 KB Output is correct
3 Correct 182 ms 100296 KB Output is correct
4 Correct 279 ms 102604 KB Output is correct
5 Correct 281 ms 102348 KB Output is correct
6 Correct 328 ms 101324 KB Output is correct
7 Correct 30 ms 91728 KB Output is correct
8 Correct 150 ms 102864 KB Output is correct
9 Correct 234 ms 105812 KB Output is correct
10 Correct 443 ms 112840 KB Output is correct
11 Correct 484 ms 112892 KB Output is correct
12 Correct 457 ms 112840 KB Output is correct
13 Correct 479 ms 112844 KB Output is correct
14 Correct 444 ms 112884 KB Output is correct
15 Correct 446 ms 112628 KB Output is correct
16 Correct 480 ms 112844 KB Output is correct
17 Correct 446 ms 113340 KB Output is correct
18 Correct 511 ms 113008 KB Output is correct
19 Correct 458 ms 113100 KB Output is correct
20 Correct 495 ms 112932 KB Output is correct
21 Correct 494 ms 113036 KB Output is correct
22 Correct 454 ms 113052 KB Output is correct
23 Correct 470 ms 112932 KB Output is correct
24 Correct 462 ms 113060 KB Output is correct
25 Correct 499 ms 113052 KB Output is correct

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 88920 KB Output isn't correct
2 Halted 0 ms 0 KB -