关于暴力分数

赛时打了个暴力，每组最坏

nm

复杂度。在我的机子上过了样例1-8，样例9 1.5s 没算出来。故期望过5e4，但实则28pts，其余点全TLE。请问是全部为最差情况吗？

我当然知道

O(nm)

不为正解，也知道评测机性能差异。但在得不到数据的情况下，请各位奆佬看下，如果可以的话可否给出更优雅的暴力/正解思路?

orz

代码：

CPP

#include <bits/stdc++.h>

using namespace std;

const int N = 100005;
const int INF = 2e9;

int n, m;
int p[N];
int minR[N];
int maxL[N];

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
        minR[i] = i + 1;
        maxL[i] = i - 1;
    }
    while (m--) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            for (int l = x; l <= n; l++)if (minR[l] <= y)minR[l] = y + 1;
            for (int r = y; r >= 1; r--)if (maxL[r] >= x)maxL[r] = x - 1;
        } else {
            int ans = INF;
            for (int l = x; l >= 1; l--) {
                if (minR[l] > n) continue;
                int r = max(minR[l], y);
                if (r <= n) ans = min(ans, p[r] - p[l]);
            }
            for (int r = y; r <= n; r++) {
                if (maxL[r] < 1) continue;
                int l = min(maxL[r], x);
                if (l >= 1) ans = min(ans, p[r] - p[l]);
            }
            if (ans == INF) cout << "-1\n";
            else cout << ans << '\n';
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

讨论操作

回复

相关推荐

关于暴力分数