oj.uz

Submission #846922

# Submission time Handle Problem Language Result Execution time Memory
846922 2023-09-08T16:28:54 Z eltu0815 Ants and Sugar (JOI22_sugar) C++14
42 / 100
 1442 ms 131404 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 > 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;
    
    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:105:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  105 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
sugar.cpp: In function 'void print(int, int, int)':
sugar.cpp:121:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  121 |     int mid = str + ed >> 1;
      |               ~~~~^~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 111184 KB Output is correct
2 Correct 17 ms 111448 KB Output is correct
3 Correct 15 ms 111196 KB Output is correct
4 Correct 16 ms 111704 KB Output is correct
5 Correct 16 ms 111192 KB Output is correct
6 Incorrect 18 ms 111452 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 15 ms 111192 KB Output is correct
2 Correct 15 ms 111196 KB Output is correct
3 Correct 16 ms 111192 KB Output is correct
4 Correct 561 ms 125480 KB Output is correct
5 Correct 350 ms 120472 KB Output is correct
6 Correct 629 ms 127180 KB Output is correct
7 Correct 362 ms 120620 KB Output is correct
8 Correct 788 ms 130656 KB Output is correct
9 Correct 747 ms 131404 KB Output is correct
10 Correct 780 ms 130860 KB Output is correct
11 Correct 738 ms 131168 KB Output is correct
12 Correct 339 ms 118480 KB Output is correct
13 Correct 448 ms 122380 KB Output is correct
14 Correct 731 ms 127840 KB Output is correct
15 Correct 786 ms 127948 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 111448 KB Output is correct
2 Correct 319 ms 117892 KB Output is correct
3 Correct 448 ms 122572 KB Output is correct
4 Correct 720 ms 128132 KB Output is correct
5 Correct 734 ms 127952 KB Output is correct
6 Correct 555 ms 124416 KB Output is correct
7 Correct 40 ms 112204 KB Output is correct
8 Correct 278 ms 117980 KB Output is correct
9 Correct 496 ms 122244 KB Output is correct
10 Correct 809 ms 128436 KB Output is correct
11 Correct 898 ms 128500 KB Output is correct
12 Correct 825 ms 128380 KB Output is correct
13 Correct 743 ms 128712 KB Output is correct
14 Correct 859 ms 128440 KB Output is correct
15 Correct 536 ms 128292 KB Output is correct
16 Correct 705 ms 128376 KB Output is correct
17 Correct 1119 ms 128776 KB Output is correct
18 Correct 1290 ms 128600 KB Output is correct
19 Correct 1218 ms 128572 KB Output is correct
20 Correct 1185 ms 128572 KB Output is correct
21 Correct 1387 ms 128576 KB Output is correct
22 Correct 1442 ms 128416 KB Output is correct
23 Correct 1372 ms 128396 KB Output is correct
24 Correct 1187 ms 128716 KB Output is correct
25 Correct 1263 ms 128652 KB Output is correct

Subtask #4
0 / 52.0

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