Submission #3441894

---

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;
	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<pair<int, int> >qq;
	int nx = 0;
	int n;
	int m;
	int x, y, z;
	int xx;
	scanf("%d", &n);
	init();
	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);
		qq.push_back(make_pair(x, y));
	}
	sort(qq.begin(), qq.end());
	for (int i = 1; i <= n; i++){
		if (b[i - 1]<b[i]){
			s[i] = max(s[i - 1] + 1, s[i]);
		}
		else s[i] = max(s[i - 1], s[i]);
		if (nx < qq.size()){
			while (qq[nx].first <= i){
				xx = qq[nx].second;
				x = s[i - 1] + (xx - b[xx]) - (i - 1 - b[i - 1]);
				y = max_search(i, xx + 1, 1, 0, N);
				if (y > (-MOD)){
					y += (xx - b[xx]);
					z = max(x, y);
				}
				else z = x;
				s[xx] = max(s[xx], z);
				change(xx, z - (xx - b[xx]));
				nx++;
				if (nx >= qq.size())break;
			}
		}

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

	return 0;

}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:58:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
./Main.cpp:63:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
                  ^
./Main.cpp:73:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &m);
                 ^
./Main.cpp:75:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &x, &y);
                         ^

Judge Result