@刘恩印 不开o(2)也AC， 我不会发截图，你可以过来看一下
1 个赞
之后请卡时开O2。我烦了，我本人来把这个思路卡掉。卡完请结贴。
1 个赞
我的没有开O2
1 个赞
哥，你这个数据 lzy 1h前就给我了，我就跑0.2s/cf
1 个赞
说一下，我卡掉的是这份代码（谭立晗在信友队的AC代码）
#include <bits/stdc++.h>
#define int long long
#define PII pair<int, int>
#define ls (x << 1)
#define rs (x << 1 | 1)
const int N = 2e5 + 5;
using namespace std;
int n, ans;
int a[N], b[N], c[N];
struct Node {
int fi, se;
};
struct Tree {
int l, r;
Node mn;
} t[N << 2];
#define pushup(x) t[x].mn.fi = min(t[ls].mn.fi, t[rs].mn.fi), t[x].mn.se = min(t[ls].mn.se, t[rs].mn.se)
inline void build(int l, int r, int x) {
t[x].l = l; t[x].r = r;
if(l == r) return t[x].mn = (Node) {a[l], b[l]}, void();
int mid = (l + r) >> 1;
build(l, mid, ls); build(mid + 1, r, rs);
pushup(x);
return ;
}
inline Node Min(Node a, Node b) {
a.fi = min(a.fi, b.fi); a.se = min(a.se, b.se);
return a;
}
inline Node query(int l, int r, int x) {
if(l <= t[x].l && t[x].r <= r) return t[x].mn;
int mid = (t[x].l + t[x].r) >> 1; Node res; res.fi = res.se = 1e13;
if(l <= mid) res = Min(res, query(l, r, ls));
if(r > mid) res = Min(res, query(l, r, rs));
return res;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
mt19937 rd(19821116);
cin >> n;
for(int i = 1; i <= n; ++i) cin >> a[i] >> b[i], c[i] = i;
shuffle(c + 1, c + n + 1, rd);
build(1, n, 1);
for(int i = 1, l, r; i <= n; ++i) {
l = c[i];
for(r = l; r <= n; ++r) {
Node s = query(l, r, 1);
ans = max(ans, (r - l + 1) * s.fi * s.se);
r = l + ans / (s.fi * s.se) - 1;
}
}
cout << ans << "\n";
return 0;
}
2 个赞
你那个有没有可能把正解卡掉了
2 个赞
固定种子活该被卡
3 个赞
我并不是针对他，只不过点开了高分代码复制了一份
3 个赞
我发的是类似于楼主的做法的代码，你可以卡一下（见前前个帖
3 个赞
你卡的不是生成随机数的啊。
种子是固定的。
random_device 这种真随机的就卡不了了
3 个赞
好，我试试，但是似乎并不容易卡
3 个赞
卡的时候是不是要看一下开没开O2，正解是需要在开不开O2的时候都能AC吧
3 个赞
我丢，甚至线段树 RMQ 还是递归的，这个常数/cf
3 个赞
他的最坏复杂度还要多一个log 哥，而且是删不掉的log
也就是 O（玄学*log）
4 个赞
既然要卡，就给出数据
3 个赞