QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#948506#3861. Il Derby della MadonninaenzeWA 1ms3712kbC++204.0kb2025-03-23 06:52:472025-03-23 06:52:48

Judging History

This is the latest submission verdict.

  • [2025-03-23 06:52:48]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3712kb
  • [2025-03-23 06:52:47]
  • Submitted

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'