Submission #3441573

---

Source Code Expand

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<functional>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
#define MOD 1000000007
#define f(i,n) for(int i=0;i<int(n);i++)
#define N (1<<18)

int a[(2 * N)];

void init(void){
	f(i, 2 * N)a[i] = -MOD;
	return;
}


void change(int k, int x){
	k += N - 1;
	if(a[k]<x)a[k] = x;
else return;
	while (k > 1){
		k = k / 2;
		a[k] = max(a[2 * k], a[2 * k + 1]);
	}
	return;
}
//探索(0<=l<r<=n)範囲は(l<=x<r)初期は(l,r,1,0,N)
int max_search(int l, int r, int k, int sl, int sr){
	if (r <= sl || sr <= l)return -MOD;
	else if (l <= sl&&sr <= r) return a[k];
	else{
		int vl = max_search(l, r, 2 * k, sl, (sl + sr) / 2);
		int vr = max_search(l, r, 2 * k + 1, (sl + sr) / 2, sr);
		return max(vl, vr);
	}
}




int main(void){
int b[N];
int s[N];
vector<int>q[N];
int n;
int m;
int x,y,z;
init();
scanf("%d",&n);
b[0]=0;
s[0]=b[0];
f(i,n){
scanf("%d",&x);
if(x==0){
b[i+1]=b[i]+1;
s[i+1]=b[i+1];
}
else{
b[i+1]=b[i];
s[i+1]=b[i+1];
}
}
scanf("%d",&m);
f(i,m){
scanf("%d %d",&x,&y);
q[x].push_back(y);
}
for(int i=1;i<=n;i++){
if(b[i-1]<b[i]){
s[i]=max(s[i-1]+1,s[i]);
}

f(j,q[i].size()){
x=s[i-1]+(q[i][j]-b[q[i][j]])-(i-1-b[i-1]);
y=max_search(i,q[i][j]+1,1,0,N);
if(y>(-MOD)){
y+=(q[i][j]-b[q[i][j]]);
z=max(x,y);
}
else z=x;
s[q[i][j]]=max(s[q[i][j]],z);
change(q[i][j],z-(q[i][j]-b[q[i][j]]));
}

}
printf("%d\n",n-s[n]);


return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:57:15: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 scanf("%d",&n);
               ^
./Main.cpp:61:15: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 scanf("%d",&x);
               ^
./Main.cpp:71:15: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 scanf("%d",&m);
               ^
./Main.cpp:73:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 scanf("%d %d",&x,&y);
                     ^

Judge Result