QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#388686 | #6104. Building Bombing | MladenP# | WA | 1ms | 7824kb | C++14 | 2.9kb | 2024-04-13 18:05:08 | 2024-04-13 18:05:08 |
Judging History
answer
#include <bits/stdc++.h>
#define mid ((l+r)/2)
using namespace std;
const int MAXN = 100010;
const int MAXK = 15;
const int INF = 1000000000;
int N, L, K;
set<int> s;
map<int, int> mp;
int seg[4*MAXN], lazy[4*MAXN], h[MAXN], dp[MAXN][MAXK];
void init1(int node, int l, int r) {
seg[node] = 0;
lazy[node] = 0;
if (l != r) {
init1(2*node, l, mid);
init1(2*node+1, mid+1, r);
}
}
void init2(int node, int l, int r) {
seg[node] = INF;
lazy[node] = 0;
if (l != r) {
init2(2*node, l, mid);
init2(2*node+1, mid+1, r);
}
}
void propagate(int node, int l, int r) {
if (lazy[node]) {
seg[node] += lazy[node];
if (l != r) {
lazy[2*node] += lazy[node];
lazy[2*node+1] += lazy[node];
}
lazy[node] = 0;
}
}
void update(int node, int l, int r, int L, int R, int val) {
propagate(node, l, r);
if (L <= l && r <= R) {
lazy[node] += val;
propagate(node, l, r);
return;
}
if (L <= mid) update(2*node, l, mid, L, R, val);
if (R > mid) update(2*node+1, mid+1, r, L, R, val);
seg[node] = min(seg[2*node], seg[2*node+1]);
}
int query(int node, int l, int r, int L, int R) {
propagate(node, l, r);
if (R < L || r < l || R < l || r < L) {
//cerr << "OUT: " << node << ' ' << l << ' ' << r << ' ' << L << ' ' << R << endl;
return INF;
}
if (L <= l && r <= R) {
//cerr << "SEG: " << node << ' ' << l << ' ' << r << ' ' << L << ' ' << R << ' ' << seg[node] << endl;
return seg[node];
}
return min(query(2*node, l, mid, L, R), query(2*node+1, mid+1, r, L, R));
}
int main() {
cin >> N >> L >> K;
for (int i = 1; i <= N; i++) {
cin >> h[i];
s.insert(h[i]);
}
int sol = 0;
for (int i = 1; i < L; i++) {
if (h[i] >= h[L]) sol++;
}
int idxx = 1;
for (auto x : s) {
mp[x] = idxx;
idxx++;
}
for (int i = 1; i <= N+1; i++) {
h[i] = mp[h[i]];
//cout << h[i] << ' ';
dp[i][0] = INF;
}
for (int k = 1; k <= K; k++) {
if (k == 1) init1(1, 1, N);
else init2(1, 1, N);
for (int i = N; i >= 1; i--) {
//cerr << "K=" << k << endl;
//cerr << "BANAN1" << endl;
dp[i][k] = (h[i] == N ? (k==1 ? 0:INF):query(1, 1, N, h[i]+1, N));
//cerr << i << ' ' << k << ' ' << dp[i][k] << endl;
//cerr << "BANAN2" << endl;
update(1, 1, N, 1, h[i], +1);
//cerr << "BANAN3" << endl;
int temp = query(1, 1, N, h[i], h[i]);
//cerr << "BANAN4" << endl;
if (dp[i][k-1] < temp) update(1, 1, N, h[i], h[i], dp[i][k-1]-temp);
}
}
//cerr << sol << ' ' << dp[L][K] << endl;
cout << (dp[L][K]+sol >= INF ? -1 : dp[L][K]+sol);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7636kb
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: 1ms
memory: 5732kb
input:
3 2 2 30 20 10
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 7692kb
input:
1 1 1 608954134
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 0ms
memory: 7824kb
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: 1ms
memory: 5716kb
input:
10 4 2 31201623 546478688 709777934 672927273 672927273 709777934 801718395 672927273 926114576 38983342
output:
2
result:
wrong answer 1st numbers differ - expected: '3', found: '2'