QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#528006 | #6104. Building Bombing | suspicious-impostor | WA | 0ms | 27904kb | C++20 | 5.3kb | 2024-08-23 02:29:22 | 2024-08-23 02:29:22 |
Judging History
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;
for(ll i : ord){
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);
lztree::modify(i,nval);
if(i==l)
{ans=nval[k-1];break;}
}
for(int i : rep(l))
if(a[i]>=a[l]) ans++;
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();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 27256kb
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: 27440kb
input:
3 2 2 30 20 10
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 27904kb
input:
1 1 1 608954134
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 27080kb
input:
10 5 3 872218248 517822599 163987167 517822599 458534407 142556631 142556631 458534407 458534407 872218248
output:
4
result:
wrong answer 1st numbers differ - expected: '-1', found: '4'