QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#107342#6104. Building Bombingbulijiojiodibuliduo#WA 159ms8256kbC++2.6kb2023-05-21 00:22:122023-05-21 00:22:15

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-21 00:22:15]
  • 评测
  • 测评结果:WA
  • 用时:159ms
  • 内存:8256kb
  • [2023-05-21 00:22:12]
  • 提交

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);
}

Details

Tip: Click on the bar to expand more detailed information

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'