Submission #1195582

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195582		vjudge2	JOI tour (JOI24_joitour)	C++20	16 / 100	230 ms	43608 KiB

joitour

#include "joitour.h"
#include <bits/stdc++.h>
using namespace std;

using i32 = int32_t;
#define int long long
const int N = 2e5 + 5;
int n, f[N];

struct Node {
    int a0, a1, a2, a01, a12, a10, a21, a012, a210;
} dummy;

Node merge(Node lhs, Node rhs) {
    Node res;
    res.a0 = lhs.a0 + rhs.a0;
    res.a1 = lhs.a1 + rhs.a1;
    res.a2 = lhs.a2 + rhs.a2;
    res.a01 = lhs.a0 * rhs.a1 + lhs.a01 + rhs.a01;
    res.a12 = lhs.a1 * rhs.a2 + lhs.a12 + rhs.a12;
    res.a10 = lhs.a1 * rhs.a0 + lhs.a10 + rhs.a10;
    res.a21 = lhs.a2 * rhs.a1 + lhs.a21 + rhs.a21;
    res.a012 = lhs.a0 * rhs.a12 + lhs.a01 * rhs.a2 + lhs.a012 + rhs.a012;
    res.a210 = lhs.a2 * rhs.a10 + lhs.a21 * rhs.a0 + lhs.a210 + rhs.a210;
    return res;
}

struct SegTree {
    int size = 1;
    vector<Node> seg;
    void init(int sz) {
        while (size < sz) size *= 2;
        seg.assign(2 * size + 10, dummy);
    }
    void update(int pos, int v, int l, int r, int id) {
        if (l == r) {
            seg[id] = dummy;
            if (v == 0) seg[id].a0++;
            else if (v == 1) seg[id].a1++;
            else seg[id].a2++;
            return;
        }
        int mid = (l + r) / 2;
        if (pos <= mid) update(pos, v, l, mid, id * 2);
        else update(pos, v, mid + 1, r, id * 2 + 1);
        seg[id] = merge(seg[id * 2], seg[id * 2 + 1]);
    }
    Node query(int ql, int qr, int l, int r, int id) {
        if (ql <= l && r <= qr) return seg[id];
        if (qr < l || r < ql) return dummy;
        int mid = (l + r) / 2;
        return merge(query(ql, qr, l, mid, id * 2), query(ql, qr, mid + 1, r, id * 2 + 1));
    }
} ST;

void init(i32 _N, std::vector<i32> F, std::vector<i32> U, std::vector<i32> V,
          i32 Q) {
    n = _N;
    ST.init(n+1);
    for (int i = 0; i < n; i++) {
        f[i] = F[i];
        ST.update(i+1, f[i], 1, n, 1);
    }
}

void change(i32 X, i32 Y) {
    X++;
    ST.update(X, Y, 1, n, 1);
}

int num_tours() {
    Node res = ST.query(1, n, 1, n, 1);
    return res.a012 + res.a210;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 6
• Subtask 4: 16 / 16
• Subtask 5: 0 / 16
• Subtask 6: 0 / 34
• Subtask 7: 0 / 14