Codeforces 924D Contact ATC (看题解)

Contact ATC

我跑去列方程, 然后就gg了。。。

我们计每个飞机最早到达时间为L[ i ], 最晚到达时间为R[ i ],

对于面对面飞行的一对飞机, 只要他们的时间有交集则必定满足条件。

对于相同方向飞行的飞机, 只有其中一个的时间包含另一个的时间才满足条件。

#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(-); struct Bit {
int a[N];
void init() {
memset(a, , sizeof(a));
}
void modify(int x, int v) {
for(int i = x; i < N; i += i & -i)
a[i] += v;
}
int sum(int x) {
int ans = ;
for(int i = x; i; i -= i & -i)
ans += a[i];
return ans;
}
int query(int L, int R) {
if(L > R) return ;
return sum(R) - sum(L - );
}
}; struct Node {
Node(LL a, LL b) : a(a), b(b) {}
bool operator < (const Node& rhs) const {
return a * rhs.b < rhs.a * b;
}
bool operator == (const Node& rhs) const {
return a * rhs.b == rhs.a * b;
}
void print() {
printf("%.5f ", 1.0 * a / b);
}
LL a, b;
}; int n, w, x[N], v[N];
LL ans = ;
vector<PII> vc[];
vector<Node> hs;
Bit bit; bool cmp(PII& a, PII& b) {
if(a.fi == b.fi) return a.se < b.se;
return a.fi > b.fi;
} LL solve(vector<PII>& vc) {
bit.init();
LL ans = ;
sort(vc.begin(), vc.end(), cmp);
for(int i = ; i < SZ(vc); i++) {
ans += bit.sum(vc[i].se);
bit.modify(vc[i].se, );
}
return ans;
} int main() {
scanf("%d%d", &n, &w);
for(int i = ; i <= n; i++) {
scanf("%d%d", &x[i], &v[i]);
if(x[i] < ) {
hs.push_back(Node(-x[i], v[i] + w));
hs.push_back(Node(-x[i], v[i] - w));
} else {
hs.push_back(Node(x[i], w - v[i]));
hs.push_back(Node(x[i], -w - v[i]));
}
}
sort(hs.begin(), hs.end());
hs.erase(unique(hs.begin(), hs.end()), hs.end());
for(int i = ; i <= n; i++) {
if(x[i] < ) {
int L = lower_bound(hs.begin(), hs.end(), Node(-x[i], v[i] + w)) - hs.begin() + ;
int R = lower_bound(hs.begin(), hs.end(), Node(-x[i], v[i] - w)) - hs.begin() + ;
vc[].push_back(mk(L, R));
} else {
int L = lower_bound(hs.begin(), hs.end(), Node(x[i], w - v[i])) - hs.begin() + ;
int R = lower_bound(hs.begin(), hs.end(), Node(x[i], -w - v[i])) - hs.begin() + ;
vc[].push_back(mk(L, R));
}
}
ans += solve(vc[]);
ans += solve(vc[]);
ans += 1ll * SZ(vc[]) * SZ(vc[]);
bit.init();
for(auto& t : vc[]) bit.modify(t.se, );
for(auto& t : vc[]) ans -= bit.sum(t.fi - );
bit.init();
for(auto& t : vc[]) bit.modify(t.fi, );
for(auto& t : vc[]) ans -= bit.query(t.se + , N - );
printf("%lld\n", ans);
return ;
} /*
*/
上一篇:scikit-learn一般实例之一:保序回归(Isotonic Regression)


下一篇:mysql 开启慢查询 如何打开mysql的慢查询日志记录