oj.uz

Submission #846532

# Submission time Handle Problem Language Result Execution time Memory
846532 2023-09-07T17:51:47 Z eltu0815 Ants and Sugar (JOI22_sugar) C++14
16 / 100
 537 ms 163092 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;
ll L;
ll arr[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) * arr[2 * 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] = seg[node].dp[1][1] = 0;
        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] = arr[2 * str - 1];
        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]);
}

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;
    init(0, q + 1 >> 1, 1);
    ll A = 0;
    for(int tt = 1; tt <= q; ++tt) {
        int t, x, v; cin >> t >> x >> v;
        arr[x] += v;
        if(t == 1) A += v, update(0, q + 1 >> 1, (x + 1)/2, 1);
        else update(0, q + 1 >> 1, x/2, 1);
        cout << A - max(max(seg[1].dp[0][0], seg[1].dp[0][1]), max(seg[1].dp[1][0], seg[1].dp[1][1])) << '\n';
//        print(0, q/2, 1);
//        cout << endl;
    }
    
    return 0;
}

Compilation message

sugar.cpp: In function 'void init(int, int, int)':
sugar.cpp:43:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |     int mid = str + ed >>1;
      |               ~~~~^~~~
sugar.cpp: In function 'void update(int, int, int, int)':
sugar.cpp:54:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
sugar.cpp: In function 'void print(int, int, int)':
sugar.cpp:63:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
sugar.cpp: In function 'int main()':
sugar.cpp:74:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |     init(0, q + 1 >> 1, 1);
      |             ~~^~~
sugar.cpp:79:40: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |         if(t == 1) A += v, update(0, q + 1 >> 1, (x + 1)/2, 1);
      |                                      ~~^~~
sugar.cpp:80:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |         else update(0, q + 1 >> 1, x/2, 1);
      |                        ~~^~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 80476 KB Output is correct
2 Correct 12 ms 80532 KB Output is correct
3 Incorrect 11 ms 80472 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 80476 KB Output is correct
2 Correct 11 ms 80532 KB Output is correct
3 Correct 11 ms 80476 KB Output is correct
4 Correct 376 ms 86788 KB Output is correct
5 Correct 161 ms 84132 KB Output is correct
6 Correct 451 ms 95824 KB Output is correct
7 Correct 166 ms 88500 KB Output is correct
8 Correct 512 ms 98896 KB Output is correct
9 Correct 342 ms 99624 KB Output is correct
10 Correct 537 ms 99156 KB Output is correct
11 Correct 347 ms 99616 KB Output is correct
12 Correct 152 ms 86500 KB Output is correct
13 Correct 208 ms 89148 KB Output is correct
14 Correct 343 ms 96296 KB Output is correct
15 Correct 333 ms 96084 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 74 ms 163092 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 80476 KB Output is correct
2 Correct 12 ms 80532 KB Output is correct
3 Incorrect 11 ms 80472 KB Output isn't correct
4 Halted 0 ms 0 KB -