Submission #978301

#	Time	Username	Problem	Language	Result	Execution time	Memory
978301		myheartwaving	Fish 3 (JOI24_fish3)	C++14	100 / 100	1464 ms	184396 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 300010, INF = 1e18;
struct mat {
    int a[4][4];
    mat() {
        a[1][2] = a[1][3] = a[2][1] = a[2][3] = a[3][1] = a[3][2] = 0;
        a[1][1] = a[2][2] = a[3][3] = 1;
    }
    mat operator*(const mat &m) const {
        mat ans;
////        ans.a[1][1] = a[1][1] * m.a[1][1] + a[1][2] * m.a[2][1] + a[1][3] * m.a[3][1];
        ans.a[1][1] = a[1][1] * m.a[1][1];
////        ans.a[1][2] = a[1][1] * m.a[1][2] + a[1][2] * m.a[2][2] + a[1][3] * m.a[3][2];
        ans.a[1][2] = a[1][1] * m.a[1][2] + a[1][2];
////        ans.a[1][3] = a[1][1] * m.a[1][3] + a[1][2] * m.a[2][3] + a[1][3] * m.a[3][3];
////        ans.a[2][1] = a[2][1] * m.a[1][1] + a[2][2] * m.a[2][1] + a[2][3] * m.a[3][1];
////        ans.a[2][2] = a[2][1] * m.a[1][2] + a[2][2] * m.a[2][2] + a[2][3] * m.a[3][2];
////        ans.a[2][3] = a[2][1] * m.a[1][3] + a[2][2] * m.a[2][3] + a[2][3] * m.a[3][3];
        ans.a[1][3] = 0ll;
        ans.a[2][1] = 0ll;
        ans.a[2][2] = 1ll;
        ans.a[2][3] = 0ll;
        ans.a[3][1] = a[3][1] * m.a[1][1] + a[3][3] * m.a[3][1];
        ans.a[3][2] = a[3][1] * m.a[1][2] + a[3][2] + a[3][3] * m.a[3][2];
//        ans.a[3][3] = a[3][2] * m.a[2][3] + a[3][3] * m.a[3][3];
        ans.a[3][3] = 1ll;
        return ans;
    }
};
struct SegT {
    mat t[N << 2];
    bool vis[N << 2];
    static inline int ls(int u) { return u << 1; }
    static inline int rs(int u) { return u << 1 | 1; }
    inline void pushdown(int u) {
        if (vis[u]) {
            t[ls(u)] = t[ls(u)] * t[u];
            t[rs(u)] = t[rs(u)] * t[u];
            t[u].a[1][2] = t[u].a[1][3] = t[u].a[2][1] = t[u].a[2][3] = t[u].a[3][1] = t[u].a[3][2] = 0;
            t[u].a[1][1] = t[u].a[2][2] = t[u].a[3][3] = 1;
            vis[u] = 0;
            vis[ls(u)] = vis[rs(u)] = 1;
        }
        return;
    }
    void update(const int l, const int r, const int ql, const int qr, const int u, const mat &x) {
        if (ql <= l && qr >= r) {
            t[u] = t[u] * x;
            vis[u] = 1;
//            for (int i = 1; i <= 3; i++) {
//                for (int j = 1; j <= 3; j++)cout << t[u].a[i][j] << " ";
//                cout << '\n';
//            }
            return;
        }
        int mid((l + r) >> 1);
        pushdown(u);
        if (ql <= mid)update(l, mid, ql, qr, ls(u), x);
        if (qr > mid)update(mid + 1, r, ql, qr, rs(u), x);
        return;
    }
    int query(const int l, const int r, const int u, const int pos) {
//        if (l == r) {
//            for (int i = 1; i <= 3; i++) {
//                for (int j = 1; j <= 3; j++)cout << t[u].a[i][j] << " ";
//                cout << '\n';
//            }
//            return t[u];
//        }
        if (l == r) {
            return u;
        }
        pushdown(u);
        int mid((l + r) >> 1);
        if (pos <= mid)return query(l, mid, ls(u), pos);
        else return query(mid + 1, r, rs(u), pos);
    }
};
SegT T;
int n, D, C[N], q, ans[N];
vector<pair<int, int>> qlist[N];
int check(int pos) {
    mat nw;
    nw = T.t[T.query(1, n, 1, pos)];
    return INF * nw.a[1][1] + nw.a[3][1];
}

void work() {
    for (int i = 1; i <= n; i++) {
        int l(1), r(i), now(C[i] / D);
        if (C[i] % D > C[i - 1] % D && i > 1) {
            mat tmp;
            tmp.a[3][1] = -1;
            T.update(1, n, 1, i - 1, 1, tmp);
        }
        while (l < r) {
            int mid((l + r) >> 1);
            if (check(mid) >= now)r = mid;
            else l = mid + 1;
        }
        if (l > 1) {
            mat tmp;
            tmp.a[1][2] = -1ll;
            tmp.a[3][2] = now;
            T.update(1, n, 1, l - 1, 1, tmp);
        }
        {
            mat tmp;
            tmp.a[1][1] = 0;
            tmp.a[3][1] = now;
            T.update(1, n, l, i, 1, tmp);
        }
        for (auto x: qlist[i]) {
            mat tmp = T.t[T.query(1, n, 1, x.first)];
            if (INF * tmp.a[1][1] + tmp.a[3][1] >= 0)
                ans[x.second] = INF * tmp.a[1][2] + tmp.a[3][2];
            else ans[x.second] = -1ll;
        }
//        for (int j = 1; j <= i; j++)
//            cout << check(j) << ' ';
//        cout << '\n';
    }
    return;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
//    freopen("test.in", "r", stdin);
    cin >> n >> D;
//    cout<<clock()<<'\n';
    for (int i = 1; i <= n; i++)cin >> C[n + 1 - i];
    cin >> q;
    for (int i = 1; i <= q; i++) {
        int l, r;
        cin >> l >> r;
        swap(l, r);
        l = n + 1 - l;
        r = n + 1 - r;
        qlist[r].push_back({l, i});
    }
    work();
//    for (int k = 1; k <= 5; k++) {
//        int now = T.query(1, n, 1, k);
//        for (int i = 1; i <= 3; i++) {
//            for (int j = 1; j <= 3; j++) {
//                cout << T.t[now].a[i][j] << " ";
//            }
//            cout << '\n';
//        }
//    }
    for (int i = 1; i <= q; i++)cout << ans[i] << '\n';

//    cout<<clock()<<'\n';
    return 0;
}
/*
 * 6 3
16 14 13 8 6 5
4
1 4
2 5
3 3
1 6

 */

• Subtask 1: 9 / 9
• Subtask 2: 7 / 7
• Subtask 3: 28 / 28
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36