oj.uz

Submission #1033344

# Submission time Handle Problem Language Result Execution time Memory
1033344 2024-07-24T16:56:57 Z thangdz2k7 Bitaro, who Leaps through Time (JOI19_timeleap) C++17
0 / 100
 854 ms 58024 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 5;
const long long inf = -1e18;

struct Node{
    long long val[2][2];

    Node(){
        for (int i = 0; i < 2; ++ i)
            for (int j = 0; j < 2; ++ j) val[i][j] = inf;
        val[0][0] = 0;
    }
};

Node mer(Node a, Node b){
    Node c;
    for (int i = 0; i < 2; ++ i){
        for (int j = 0; j < 2; ++ j) c.val[i][j] = max(a.val[i][j], b.val[i][j]);
    }
    for (int i = 0; i < 2; ++ i){
        for (int l = 0; l < 2; ++ l){
            for (int j = 0; j < 2; ++ j) c.val[i][j] = max(c.val[i][j], a.val[i][l] + b.val[l][j]);
        }
    }

    return c;
}

Node it[4 * N];

void update(int s, int l, int r, int u, int i, int j){
    //if (i == j && i == 3 && u == 3) cout << l << ' ' << r << ' ' << u << endl;
    if (l == r){
        it[s].val[0][0] = 0;
        it[s].val[1][0] = l - j;
        it[s].val[0][1] = i - l;
        return;
    }

    int mid = l + r >> 1;
    if (mid >= u) update(2 * s, l, mid, u, i, j);
    else update(2 * s + 1, mid + 1, r, u, i, j);
    it[s] = mer(it[2 * s], it[2 * s + 1]);
}

Node get(int s, int l, int r, int u, int v){
    if (u <= l && r <= v) return it[s];

    int mid = l + r >> 1;
    Node a, b;
    int bl = 0, br = 0;
    if (mid >= u) a = get(2 * s, l, mid, u, v), bl = 1;
    if (mid + 1 <= v) b = get(2 * s + 1, mid + 1, r, u, v), br = 1;
    if (!bl) return b;
    if (!br) return a;
    return mer(a, b);
}

int in[N], out[N], n, q;

void solve(){
    cin >> n >> q;
    for (int i = 1; i <= n - 1; ++ i){
        cin >> in[i] >> out[i];
        update(1, 0, n, i, in[i], out[i] - 1);
    }

    while (q --){
        int t; cin >> t;
        if (t & 1){
            int i; cin >> i;
            cin >> in[i] >> out[i];
            update(1, 0, n, i, in[i], out[i] - 1);
        }
        else {
            int s, ts, e, te;
            cin >> s >> ts >> e >> te;
            update(1, 0, n, s - 1, ts - 1, ts - 1);
            update(1, 0, n, e, te, te);
            //cout << t << ' ' << s << ' ' << ts << ' ' << e << ' ' << te endl;
            //cout << it[7].val[1][0] << endl;
            cout << get(1, 0, n, s - 1, e).val[0][0] << '\n';
            update(1, 0, n, s - 1, in[s - 1], out[s - 1] - 1);
            update(1, 0, n, s - 1, in[e], out[e] - 1);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();

    return 0;
}

Compilation message

timeleap.cpp: In function 'void update(int, int, int, int, int, int)':
timeleap.cpp:43:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |     int mid = l + r >> 1;
      |               ~~^~~
timeleap.cpp: In function 'Node get(int, int, int, int, int)':
timeleap.cpp:52:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
0 / 4.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 66.0

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