Submission #3441735

---

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;
	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);
		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]);
		}
		else s[i] = max(s[i - 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, 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]]));
		}
		f(j, n){
			printf("%d ", s[j + 1]);
		}
		printf("\n");
	}
	printf("%d\n", n-s[n]);

	return 0;

}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:56:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
./Main.cpp:61:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
                  ^
./Main.cpp:71:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &m);
                 ^
./Main.cpp:73: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