QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#107342 | #6104. Building Bombing | bulijiojiodibuliduo# | WA | 159ms | 8256kb | C++ | 2.6kb | 2023-05-21 00:22:12 | 2023-05-21 00:22:15 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
const int N=101000;
int n,l,k,h[N];
struct node {
int fg,mv;
}nd[4*N];
void upd(int p) {
nd[p].mv=min(nd[p+p].mv,nd[p+p+1].mv);
}
void setf(int p,int v) {
nd[p].fg+=v;
nd[p].mv+=v;
}
void build(int p,int l,int r) {
nd[p].fg=0;
nd[p].mv=1<<30;
if (l==r) {
} else {
int md=(l+r)>>1;
build(p+p,l,md);
build(p+p+1,md+1,r);
upd(p);
}
}
void push(int p) {
if (nd[p].fg) {
setf(p+p,nd[p].fg);
setf(p+p+1,nd[p].fg);
nd[p].fg=0;
}
}
int query(int p,int l,int r,int tl,int tr) {
if (tl==l&&tr==r) return nd[p].mv;
else {
push(p);
int md=(l+r)>>1;
if (tr<=md) return query(p+p,l,md,tl,tr);
else if (tl>md) return query(p+p+1,md+1,r,tl,tr);
else return min(query(p+p,l,md,tl,md),query(p+p+1,md+1,r,md+1,tr));
}
}
void modify(int p,int l,int r,int tl,int tr,int v) {
if (tl>tr) return;
if (tl==l&&tr==r) return setf(p,v);
else {
push(p);
int md=(l+r)>>1;
if (tr<=md) modify(p+p,l,md,tl,tr,v);
else if (tl>md) modify(p+p+1,md+1,r,tl,tr,v);
else modify(p+p,l,md,tl,md,v),modify(p+p+1,md+1,r,md+1,tr,v);
upd(p);
}
}
void change(int p,int l,int r,int x,int v) {
if (l==r) nd[p].mv=v;
else {
push(p);
int md=(l+r)>>1;
if (x<=md) change(p+p,l,md,x,v);
else change(p+p+1,md+1,r,x,v);
upd(p);
}
}
int dp[14][N];
int main() {
scanf("%d%d%d",&n,&l,&k);
int m=0;
vector<PII> v;
int cc=0;
rep(i,1,n+1) {
scanf("%d",&h[i]);
if (i>l&&h[i]>h[l]) v.pb(mp(-h[i],++m));
}
rep(i,1,n+1) if (i<l&&h[i]>=h[l]) ++cc;
n=m;
sort(all(v));
rep(i,0,m) {
h[v[i].se]=m-i;
}
++n; h[n]=n;
//rep(i,1,n+1) printf("%d ",h[i]); puts("");
rep(i,1,n+1) dp[0][i]=i-1;
rep(j,1,k) {
build(1,0,n);
rep(i,1,n+1) {
dp[j][i]=query(1,0,n,0,h[i]-1);
modify(1,0,n,0,h[i]-1,1);
change(1,0,n,h[i],dp[j-1][i]);
//printf("%d %d %d\n",j,i,dp[j][i]);
}
}
int ans=dp[k-1][n]+cc;
if (ans>n) ans=-1;
printf("%d\n",ans);
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 3576kb
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: 3580kb
input:
3 2 2 30 20 10
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: 0
Accepted
time: 2ms
memory: 3564kb
input:
1 1 1 608954134
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 2ms
memory: 3588kb
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: 0
Accepted
time: 2ms
memory: 3684kb
input:
10 4 2 31201623 546478688 709777934 672927273 672927273 709777934 801718395 672927273 926114576 38983342
output:
3
result:
ok 1 number(s): "3"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3756kb
input:
10 2 3 376738377 852081435 10550876 40942086 10550876 10550876 697114820 40942086 473788030 10550876
output:
-1
result:
ok 1 number(s): "-1"
Test #7:
score: 0
Accepted
time: 2ms
memory: 3748kb
input:
10 1 2 216184450 216184450 488086371 73015591 802501830 860488380 488086371 643751501 979419002 860488380
output:
3
result:
ok 1 number(s): "3"
Test #8:
score: 0
Accepted
time: 2ms
memory: 3772kb
input:
10 4 5 81167617 293949746 274292711 760663226 760663226 373523484 261723185 760663226 261723185 713804678
output:
-1
result:
ok 1 number(s): "-1"
Test #9:
score: 0
Accepted
time: 2ms
memory: 3704kb
input:
10 1 10 8775290 171732800 240074429 560150106 594414689 615008126 693779505 808555946 960743397 991906871
output:
0
result:
ok 1 number(s): "0"
Test #10:
score: 0
Accepted
time: 2ms
memory: 3632kb
input:
10 3 10 756674120 838411846 543989864 756674120 513122553 460005403 513122553 985890594 985890594 985890594
output:
-1
result:
ok 1 number(s): "-1"
Test #11:
score: 0
Accepted
time: 2ms
memory: 3736kb
input:
1 1 2 270411237
output:
-1
result:
ok 1 number(s): "-1"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
1 1 10 526049243
output:
-1
result:
ok 1 number(s): "-1"
Test #13:
score: 0
Accepted
time: 2ms
memory: 3764kb
input:
9 1 10 264254461 350329437 354458165 361860512 455656110 705176463 823349533 901851526 968433321
output:
-1
result:
ok 1 number(s): "-1"
Test #14:
score: 0
Accepted
time: 10ms
memory: 4020kb
input:
100000 96719 10 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 3643...
output:
-1
result:
ok 1 number(s): "-1"
Test #15:
score: 0
Accepted
time: 159ms
memory: 8256kb
input:
100000 2497 5 343693559 278257334 676244785 747854142 264361825 95333041 776651570 594011112 873418698 621428434 786267296 768933320 42014826 78577061 184127759 609382698 742865448 244899891 900674947 239300558 403763537 971259502 527902246 463159146 534953311 681716687 25155119 381556831 892857155 ...
output:
2368
result:
ok 1 number(s): "2368"
Test #16:
score: -100
Wrong Answer
time: 16ms
memory: 4316kb
input:
100000 92400 8 868958568 811740770 68445106 478059498 416417069 21575964 450624368 808476181 342985254 360591658 646117800 592265888 973799101 964009069 226577201 51499379 892758433 666404354 455887531 525819830 939131873 923403705 336093706 11560544 887737943 162368659 379520302 113187738 458771468...
output:
-1
result:
wrong answer 1st numbers differ - expected: '40990', found: '-1'