QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#528009#6104. Building Bombingsuspicious-impostorWA 3ms28364kbC++205.8kb2024-08-23 02:46:072024-08-23 02:46:07

Judging History

你现在查看的是最新测评结果

  • [2024-08-23 02:46:07]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:28364kb
  • [2024-08-23 02:46:07]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T>
ostream_iterator<T> oit(const string &s = " "){ return ostream_iterator<T>(cout,s.c_str()); }
inline auto rep(int l, int r) { return views::iota(min(l, r), r); }
inline auto rep(int n) { return rep(0, n); }
inline auto rep1(int l, int r) { return rep(l, r + 1); }
inline auto rep1(int n) { return rep(1, n + 1); }
inline auto per(int l, int r) { return rep(l, r) | views::reverse; }
inline auto per(int n) { return per(0, n); }
inline auto per1(int l, int r) { return per(l, r + 1); }
inline auto per1(int n) { return per(1, n + 1); }
#define A(a) begin(a),end(a)
inline auto len = ranges::ssize;

struct chash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
template<typename T, typename U> using pb_map = gp_hash_table<T, U, chash>;
template<typename T> using pb_set = gp_hash_table<T, null_type, chash>;
#define K first
#define V second

using ll = long long;
using ld = long double;

using vi = vector<int>;
using vii = vector<vector<int>>;
typedef vector<ll> vll;
using pll = pair<ll,ll>;
using pii = pair<int,int>;

constexpr ll N = 1e5, M = 1000000007, L = 17;

#define G(x) ll x; cin >> x;
#define F(i, l, r) for(ll i = l; i < (r); ++i)
#define FD(i, r, l) for(ll i = r - 1; i > (l); --i)

const ll oo = 1e14;
namespace lztree {
    const int m = 10;
    using vec = array<ll,10>;
    typedef vec T;
    typedef vec U;

    T idT = {oo,oo,oo,oo,oo,oo,oo,oo,oo,oo}, t[2 * N];
    U idU = {}, d[N];
    ll x = (fill_n(d, N, idU), 0);

    // combining segtree nodes a and b
    T f(T a, T b) { 
        for(int i : rep(m)) a[i]=min(a[i],b[i]);    
        return a; 
    }
    // applying updates a and b (in that order)
    U g(U b, U a) { 
        for(int i : rep(m)) a[i]+=b[i];    
        return a; 
    }
    // applying update b to segtree node a
    T h(U b, T a) { 
        for(int i : rep(m)) a[i]+=b[i];    
        return a; 
    }

    void calc(ll p) { t[p] = h(d[p], f(t[p * 2], t[p * 2 + 1])); }

    void apply(ll p, U v) {
        t[p] = h(v, t[p]);
        if(p < N) d[p] = g(v, d[p]);
    }

    void push(ll p) {
        p += N;
        FD(s, L, 0) {
            ll i = p >> s;
            if(d[i] != idU) {
                apply(i * 2, d[i]);
                apply(i * 2 + 1, d[i]);
                d[i] = idU;
            }
        }
    }

    void modify(ll p, T v) {
        push(p);
        t[p += N] = v;
        while(p > 1) calc(p /= 2);
    }
    void modify(ll p,ll j, ll x) {
        push(p);
        t[p += N][j] = x;
        while(p > 1) calc(p /= 2);
    }
    void modify(ll l, ll r, U v) {
        push(l), push(r - 1);
        bool cl = false, cr = false;
        for(l += N, r += N; l < r; l /= 2, r /= 2) {
            if(cl) calc(l - 1);
            if(cr) calc(r);
            if(l & 1) apply(l++, v), cl = true;
            if(r & 1) apply(--r, v), cr = true;
        }
        for(--l; r; l /= 2, r /= 2) {
            if(cl) calc(l);
            if(cr) calc(r);
        }
    }

    T query(ll l, ll r) {
        push(l), push(r - 1);
        T resl = idT, resr = idT;
        for(l += N, r += N; l < r; l /= 2, r /= 2) {
            if(l & 1) resl = f(resl, t[l++]);
            if(r & 1) resr = f(t[--r], resr);
        }
        return f(resl, resr);
    }
}
namespace seg {
    typedef ll T;
    T id=0;
    T f(T a, T b) {return a+b;}

    T t[2 * N];
    ll n=N;  // array size

    void modify(ll p, T value) {  // set value at position p
      for (p+=n, t[p] = value; p /= 2;) t[p] = f(t[2*p], t[2*p+1]);
    }

    T query(ll l, ll r) { // fold f on interval [l, r)
      T resl=id, resr=id;
      for (l += n, r += n; l < r; l /= 2, r /= 2) {
        if (l&1) resl = f(resl, t[l++]);
        if (r&1) resr = f(t[--r], resr);
      }
      return f(resl, resr);
    }
}

void run()
{
    ll n,l,k; cin >> n >> l >> k,--l;
    vll a(n); for(ll &x : a) cin >> x;
    vll ord(n),large(n); iota(A(ord),0);

    ranges::sort(ord,[&](ll i,ll j){ 
        if(a[i]==a[j]) return i>j;
        return a[i]>a[j];
    });
    
    lztree::vec ones;
    ranges::fill(ones,1);
    ll ans = 0;
    vll stk;
    vector<lztree::vec> v;

    for(ll last = -1; ll i : ord){
        if(a[i] not_eq last){
            int sz = len(stk);
            ranges::reverse(v),ranges::reverse(stk);
            for(int j : rep(sz)){
                for(auto &x : v[j]) x+=j;
                lztree::modify(stk[j],v[j]);
            }
            last=a[i],stk.clear(),v.clear();
        }
        auto qr {lztree::query(i+1,n)};
        lztree::vec nval {lztree::idT};
        for(ll j : rep(k)){
            if(!j) nval[j] = seg::query(i,n); //total things geq to it, to the right of it
            else{
                nval[j] = qr[j-1];
            }
        }
        seg::modify(i,1);
        lztree::modify(i,n,ones);
        stk.push_back(i),v.push_back(nval);
        if(i==l)
            {ans=nval[k-1];break;}
    }

    for(int i : rep(l))
        if(a[i]>=a[l]) ans++;
    // ranges::copy(a,oit<ll>()),cout << endl;
    std::cout << (ans>=oo ? -1 : ans) << '\n';
}

int main()
{
    //KING OF THE WORLD...... U.W.T.B
    cin.tie(0);
    ranges::fill(lztree::t,lztree::idT);
    run();
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 27576kb

input:

7 2 3
10 30 90 40 60 60 80

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 0ms
memory: 28304kb

input:

3 2 2
30 20 10

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

score: 0
Accepted
time: 0ms
memory: 27016kb

input:

1 1 1
608954134

output:

0

result:

ok 1 number(s): "0"

Test #4:

score: 0
Accepted
time: 3ms
memory: 27076kb

input:

10 5 3
872218248 517822599 163987167 517822599 458534407 142556631 142556631 458534407 458534407 872218248

output:

-1

result:

ok 1 number(s): "-1"

Test #5:

score: -100
Wrong Answer
time: 3ms
memory: 28364kb

input:

10 4 2
31201623 546478688 709777934 672927273 672927273 709777934 801718395 672927273 926114576 38983342

output:

5

result:

wrong answer 1st numbers differ - expected: '3', found: '5'