QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#948506 | #3861. Il Derby della Madonnina | enze | WA | 1ms | 3712kb | C++20 | 4.0kb | 2025-03-23 06:52:47 | 2025-03-23 06:52:48 |
Judging History
answer
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define pb push_back
const ld pi = 3.14159265358979323846;
const int mod = 998244353;
const ll INF = 1e18;
template<typename T>
T chmax(T a, T b) {
return a > b ? a : b;
}
template<typename T>
T chmin(T a, T b) {
return a > b ? b : a;
}
const int N = (int)3e6 + 1, M = N * 2;
template<class Operation, class Mark>
struct SegTree{
const int n;
vector<Operation> op;
vector<Mark> mrk;
SegTree(int n) : n(n), op(4 << __lg(n)), mrk(4 << __lg(n)){
function<void(int, int, int)> build = [&](int u, int l, int r){
op[u] = Operation();
if(l == r) return;
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
};
build(1, 1, n);
}
void pushup(int u){
op[u] = op[u << 1] + op[u << 1 | 1];
}
void modify(int u, const Mark &mk){
op[u].modify(mk);
mrk[u].modify(mk);
}
void pushdown(int u) {
modify(u << 1, mrk[u]);
modify(u << 1 | 1, mrk[u]);
mrk[u] = Mark();
}
void update(int u, int l, int r, int x, const Operation &v){
if(l == r){
op[u] = v;
return;
}
int m = (l + r) >> 1;
pushdown(u);
if(x <= m){
update(u << 1, l, m, x, v);
}
else{
update(u << 1 | 1, m + 1, r, x, v);
}
pushup(u);
}
void update(int u, const Operation &v){
update(1, 1, n, u, v);
}
Operation query(int u, int l, int r, int x, int y){
if(x <= l && r <= y) {
return op[u];
}
int m = (l + r) >> 1;
Operation cur;
pushdown(u);
if(x <= m){
cur = query(u << 1, l, m, x, y);
}
if(y > m){
cur = cur + query(u << 1 | 1, m + 1, r, x, y);
}
return cur;
}
Operation query(int l, int r){
return query(1, 1, n, l, r);
}
void range_update(int u, int l, int r, int x, int y, const Mark &v){
if(l >= x && r <= y){
modify(u, v);
return;
}
int m = (l + r) >> 1;
pushdown(u);
if(x <= m){
range_update(u << 1, l, m, x, y, v);
}
if(y > m){
range_update(u << 1 | 1, m + 1, r, x, y, v);
}
pushup(u);
}
void range_update(int l, int r, const Mark &v){
return range_update(1, 1, n, l, r, v);
}
};
struct Mark{
void modify(const Mark &v){
}
};
struct Operation {
int max = 0;
Operation(int p = 0){
max = p;
}
void modify(const Mark &v){
}
};
Operation operator+(Operation a, Operation b){
return {chmax(a.max, b.max)};
}
void solve(){
int n, v;
cin >> n >> v;
vector<int> a(n + 1), b(n + 1);
for(int i = 1; i <= n; i++){
cin >> a[i];
}
for(int i = 1; i <= n; i++){
cin >> b[i];
}
vector<pair<ll, ll>> p;
for(int i = 1; i <= n; i++){
if(v * a[i] >= b[i]){
p.pb({1ll * v * a[i] - b[i], 1ll * v * a[i] + b[i]});
}
}
sort(p.begin(), p.end());
vector<ll> dp;
for(int i = 0; i < p.size(); i++){
if(dp.empty() || p[i].second >= dp.back()){
dp.pb(p[i].second);
}
else{
dp[upper_bound(dp.begin(), dp.end(), p[i].second) - dp.begin()] = p[i].second;
}
}
cout << dp.size() << endl;
}
int main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
// cin >> t;
while(t--){
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3712kb
input:
3 2 5 10 15 7 17 29
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
5 1 5 7 8 11 13 3 3 -2 -2 4
output:
3
result:
ok single line: '3'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
1 2 3 7
output:
0
result:
ok single line: '0'
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3712kb
input:
1 1000000 1000000000 -1000000000
output:
0
result:
wrong answer 1st lines differ - expected: '1', found: '0'