QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#388650	#6104. Building Bombing	MladenP^#	WA	1ms	3744kb	C++14	6.4kb	2024-04-13 17:51:51	2024-04-13 17:51:53

Judging History

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

[2024-04-13 17:51:53]
评测

测评结果：WA
用时：1ms
内存：3744kb

查看

[2024-04-13 17:51:51]
提交

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]);
    }
    h[N+1] = INF;
    s.insert(h[N+1]);
    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;
    }
    dp[N+1][0] = 0;
    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 ? 0: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;
}
/*
7 2 3
 10 30 90 40 60 60 80
K=1
SEG: 7 7 7 6 7 1000000000
SEG: 13 6 6 6 7 1000000000
OUT: 12 5 5 6 7
OUT: 2 1 4 6 7
7 1 1000000000
OUT: 7 7 7 5 5
OUT: 13 6 6 5 5
SEG: 12 5 5 5 5 1000000001
OUT: 2 1 4 5 5
K=1
SEG: 3 5 7 5 7 1000000000
OUT: 2 1 4 5 7
6 1 1000000000
OUT: 3 5 7 4 4
SEG: 11 4 4 4 4 1000000002
OUT: 10 3 3 4 4
OUT: 4 1 2 4 4
K=1
SEG: 3 5 7 5 7 1000000000
OUT: 2 1 4 5 7
5 1 1000000000
OUT: 3 5 7 4 4
SEG: 11 4 4 4 4 1000000003
OUT: 10 3 3 4 4
OUT: 4 1 2 4 4
K=1
SEG: 3 5 7 4 7 1000000000
SEG: 11 4 4 4 7 1000000003
OUT: 10 3 3 4 7
OUT: 4 1 2 4 7
4 1 1000000000
OUT: 3 5 7 3 3
OUT: 11 4 4 3 3
SEG: 10 3 3 3 3 1000000004
OUT: 4 1 2 3 3
K=1
SEG: 7 7 7 7 7 1000000000
OUT: 6 5 6 7 7
OUT: 2 1 4 7 7
3 1 1000000000
OUT: 7 7 7 6 6
SEG: 13 6 6 6 6 1000000001
OUT: 12 5 5 6 6
OUT: 2 1 4 6 6
K=1
SEG: 3 5 7 3 7 1000000000
SEG: 5 3 4 3 7 1000000004
OUT: 4 1 2 3 7
2 1 1000000000
OUT: 3 5 7 2 2
OUT: 5 3 4 2 2
SEG: 9 2 2 2 2 1000000006
OUT: 8 1 1 2 2
K=1
SEG: 3 5 7 2 7 1000000000
SEG: 5 3 4 2 7 1000000004
SEG: 9 2 2 2 7 1000000006
OUT: 8 1 1 2 7
1 1 1000000000
OUT: 3 5 7 1 1
OUT: 5 3 4 1 1
OUT: 9 2 2 1 1
SEG: 8 1 1 1 1 1000000007
K=2
SEG: 7 7 7 6 7 1000000000
SEG: 13 6 6 6 7 1000000000
OUT: 12 5 5 6 7
OUT: 2 1 4 6 7
7 2 1000000000
OUT: 7 7 7 5 5
OUT: 13 6 6 5 5
SEG: 12 5 5 5 5 1000000001
OUT: 2 1 4 5 5
K=2
SEG: 3 5 7 5 7 1000000000
OUT: 2 1 4 5 7
6 2 1000000000
OUT: 3 5 7 4 4
SEG: 11 4 4 4 4 1000000002
OUT: 10 3 3 4 4
OUT: 4 1 2 4 4
K=2
SEG: 3 5 7 5 7 1000000000
OUT: 2 1 4 5 7
5 2 1000000000
OUT: 3 5 7 4 4
SEG: 11 4 4 4 4 1000000003
OUT: 10 3 3 4 4
OUT: 4 1 2 4 4
K=2
SEG: 3 5 7 4 7 1000000000
SEG: 11 4 4 4 7 1000000003
OUT: 10 3 3 4 7
OUT: 4 1 2 4 7
4 2 1000000000
OUT: 3 5 7 3 3
OUT: 11 4 4 3 3
SEG: 10 3 3 3 3 1000000004
OUT: 4 1 2 3 3
K=2
SEG: 7 7 7 7 7 1000000000
OUT: 6 5 6 7 7
OUT: 2 1 4 7 7
3 2 1000000000
OUT: 7 7 7 6 6
SEG: 13 6 6 6 6 1000000001
OUT: 12 5 5 6 6
OUT: 2 1 4 6 6
K=2
SEG: 3 5 7 3 7 1000000000
SEG: 5 3 4 3 7 1000000004
OUT: 4 1 2 3 7
2 2 1000000000
OUT: 3 5 7 2 2
OUT: 5 3 4 2 2
SEG: 9 2 2 2 2 1000000006
OUT: 8 1 1 2 2
K=2
SEG: 3 5 7 2 7 1000000000
SEG: 5 3 4 2 7 1000000004
SEG: 9 2 2 2 7 1000000006
OUT: 8 1 1 2 7
1 2 1000000000
OUT: 3 5 7 1 1
OUT: 5 3 4 1 1
OUT: 9 2 2 1 1
SEG: 8 1 1 1 1 1000000007
K=3
SEG: 7 7 7 6 7 1000000000
SEG: 13 6 6 6 7 1000000000
OUT: 12 5 5 6 7
OUT: 2 1 4 6 7
7 3 1000000000
OUT: 7 7 7 5 5
OUT: 13 6 6 5 5
SEG: 12 5 5 5 5 1000000001
OUT: 2 1 4 5 5
K=3
SEG: 3 5 7 5 7 1000000000
OUT: 2 1 4 5 7
6 3 1000000000
OUT: 3 5 7 4 4
SEG: 11 4 4 4 4 1000000002
OUT: 10 3 3 4 4
OUT: 4 1 2 4 4
K=3
SEG: 3 5 7 5 7 1000000000
OUT: 2 1 4 5 7
5 3 1000000000
OUT: 3 5 7 4 4
SEG: 11 4 4 4 4 1000000003
OUT: 10 3 3 4 4
OUT: 4 1 2 4 4
K=3
SEG: 3 5 7 4 7 1000000000
SEG: 11 4 4 4 7 1000000003
OUT: 10 3 3 4 7
OUT: 4 1 2 4 7
4 3 1000000000
OUT: 3 5 7 3 3
OUT: 11 4 4 3 3
SEG: 10 3 3 3 3 1000000004
OUT: 4 1 2 3 3
K=3
SEG: 7 7 7 7 7 1000000000
OUT: 6 5 6 7 7
OUT: 2 1 4 7 7
3 3 1000000000
OUT: 7 7 7 6 6
SEG: 13 6 6 6 6 1000000001
OUT: 12 5 5 6 6
OUT: 2 1 4 6 6
K=3
SEG: 3 5 7 3 7 1000000000
SEG: 5 3 4 3 7 1000000004
OUT: 4 1 2 3 7
2 3 1000000000
OUT: 3 5 7 2 2
OUT: 5 3 4 2 2
SEG: 9 2 2 2 2 1000000006
OUT: 8 1 1 2 2
K=3
SEG: 3 5 7 2 7 1000000000
SEG: 5 3 4 2 7 1000000004
SEG: 9 2 2 2 7 1000000006
OUT: 8 1 1 2 7
1 3 1000000000
OUT: 3 5 7 1 1
OUT: 5 3 4 1 1
OUT: 9 2 2 1 1
SEG: 8 1 1 1 1 1000000007
-1
*/

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 3744kb

input:

7 2 3
10 30 90 40 60 60 80

output:

result:

ok 1 number(s): "2"

Test #2:

score: 0

Accepted

time: 0ms

memory: 3532kb

input:

3 2 2
30 20 10

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

score: 0

Accepted

time: 0ms

memory: 3576kb

input:

1 1 1
608954134

output:

result:

ok 1 number(s): "0"

Test #4:

score: 0

Accepted

time: 1ms

memory: 3712kb

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: 0ms

memory: 3572kb

input:

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

output:

result:

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