Submission #1108715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108715		_rain_	Martian DNA (BOI18_dna)	C++14	100 / 100	88 ms	7316 KiB

dna

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define name "main"

const int N=200'000;
int n,k,R;
int d[N+2],q[N+2];

int st[N*4+2];
#define lef(id) id<<1
#define rig(id) id<<1|1
void build(int id,int l,int r){
	if (l==r) st[id]=q[l];
	else{
		int m=l+r>>1;
		build(lef(id),l,m);
		build(rig(id),m+1,r);
		st[id]=max(st[lef(id)],st[rig(id)]);
	}
}
void upd(int id,int l,int r,int p,int x){
	if (l>p||r<p) return;
	if (l==r){
		st[id]+=x;
	}
	else{
		int m=l+r>>1;
		upd(lef(id),l,m,p,x);
		upd(rig(id),m+1,r,p,x);
		st[id]=max(st[lef(id)],st[rig(id)]);
	}
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin>>n>>k>>R;
	for(int i=1;i<=n;++i) cin>>d[i],++d[i];
	for(int i=1;i<=R;++i) {
		int t;cin>>t;++t;cin>>q[t];
	}
	build(1,1,k);
	int ans=n+1;
	for(int i=1,j=1;i<=n;++i){
		while(j<=n&&st[1]>0){
			upd(1,1,k,d[j],-1);
			++j;
		}
		if (st[1]==0) ans=min(ans,j-i);
		upd(1,1,k,d[i],1);
	}
	if (ans==n+1){
		cout<<"impossible";
		exit(0);
	}
	cout<<ans;
	exit(0);
}

Compilation message (stderr)

dna.cpp: In function 'void build(int, int, int)':
dna.cpp:17:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |   int m=l+r>>1;
      |         ~^~
dna.cpp: In function 'void upd(int, int, int, int, int)':
dna.cpp:29:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |   int m=l+r>>1;
      |         ~^~

• Subtask 1: 16 / 16
• Subtask 2: 24 / 24
• Subtask 3: 28 / 28
• Subtask 4: 32 / 32