Codeforces 542A Place Your Ad Here

Place Your Ad Here

把没用的第一类区间去掉之后, 排序, 然后枚举第二类区间, 在上面死命二分就好了。

#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long long using namespace std; const int N = 2e5 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ;
const double eps = 1e-;
const double PI = acos(-); bool chkmax(LL& a, LL b) {
return a < b ? a = b, true : false;
}
bool chkmax(int& a, int b) {
return a < b ? a = b, true : false;
} int Log[N];
struct ST {
PII dp[N][];
void build(int n, PII b[]) {
for(int i = ; i <= n; i++) dp[i][] = b[i];
for(int j = ; j <= Log[n]; j++)
for(int i = ; i+(<<j)- <= n; i++)
dp[i][j] = max(dp[i][j-], dp[i+(<<(j-))][j-]);
}
PII query(int x, int y) {
int k = Log[y - x + ];
return max(dp[x][k], dp[y-(<<k)+][k]);
}
}; int n, m;
PII len[N];
PII gg = mk(, ); pair<PII, int> a[N];
pair<PII, int> b[N];
ST rmq; bool cmp(const pair<PII, int>& a, const pair<PII, int>& b) {
if(a.fi.fi == b.fi.fi) return a.fi.se > b.fi.se;
return a.fi.fi < b.fi.fi;
}
int main() {
for(int i = -(Log[]=-); i < N; i++)
Log[i] = Log[i - ] + ((i & (i - )) == );
scanf("%d%d", &n, &m);
for(int i = ; i <= n; i++) scanf("%d%d", &a[i].fi.fi, &a[i].fi.se), a[i].se = i;
for(int i = ; i <= m; i++) scanf("%d%d%d", &b[i].fi.fi, &b[i].fi.se, &b[i].se);
sort(a + , a + + n, cmp);
int up = n; n = ;
for(int i = ; i <= up; i++)
if(a[i].fi.se > a[n].fi.se) a[++n] = a[i];
// for(int i = 1; i <= n; i++) printf("%d %d %d ^^\n", a[i].se, a[i].fi.fi, a[i].fi.se);
for(int i = ; i <= n; i++) len[i].fi = a[i].fi.se - a[i].fi.fi, len[i].se = a[i].se;
rmq.build(n, len);
LL ans = ;
for(int i = ; i <= m; i++) {
int L = b[i].fi.fi, R = b[i].fi.se, c = b[i].se, len = , who = ;
int low = , high = n, p = -;
while(low <= high) {
int mid = low + high >> ;
if(a[mid].fi.fi <= L) p = mid, low = mid + ;
else high = mid - ;
}
if(~p && a[p].fi.se > L && chkmax(len, min(R, a[p].fi.se) - L)) who = a[p].se;
low = , high = n, p = -;
while(low <= high) {
int mid = low + high >> ;
if(a[mid].fi.se >= R) p = mid, high = mid - ;
else low = mid + ;
}
if(~p && a[p].fi.fi < R && chkmax(len, R - max(L, a[p].fi.fi))) who = a[p].se;
int Lb = -, Rb = -;
low = , high = n;
while(low <= high) {
int mid = low + high >> ;
if(a[mid].fi.fi >= L) Lb = mid, high = mid - ;
else low = mid + ;
}
low = , high = n;
while(low <= high) {
int mid = low + high >> ;
if(a[mid].fi.se <= R) Rb = mid, low = mid + ;
else high = mid - ;
}
if(~Lb && ~Rb && Lb <= Rb) {
PII t = rmq.query(Lb, Rb);
if(chkmax(len, t.fi)) who = t.se;
}
if(chkmax(ans, 1LL * c * len)) {
gg.fi = who;
gg.se = i;
}
}
if(ans) {
printf("%lld\n", ans);
printf("%d %d\n", gg.fi, gg.se);
} else {
puts("");
}
return ;
} /*
*/
上一篇:吴恩达机器学习笔记42-大边界的直观理解(Large Margin Intuition)


下一篇:标签