Eugeny and Array
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Eugeny has array a = a1, a2, ..., an,
consisting of n integers. Each integer ai equals
to -1, or to 1. Also, he has m queries:
- Query number i is given as a pair of integers li, ri (1 ≤ li ≤ ri ≤ n).
-
The response to the query will be integer 1, if the elements of array a can
be rearranged so as the sum ali + ali + 1 + ... + ari = 0,
otherwise the response to the query will be integer 0.
Help Eugeny, answer all his queries.
Input
The first line contains integers n and m (1 ≤ n, m ≤ 2·105).
The second line contains n integers a1, a2, ..., an (ai = -1, 1).
Next mlines contain Eugene's queries. The i-th line
contains integers li, ri (1 ≤ li ≤ ri ≤ n).
Output
Print m integers — the responses to Eugene's queries in the order they occur in the input.
Sample test(s)
input
2 3 1 -1 1 1 1 2 2 2
output
0 1 0
input
5 5 -1 1 1 1 -1 1 1 2 3 3 5 2 5 1 5
output
0 1 0 1 0
思路:询问的的长度是 -1的1的最少数的2倍以内则可以.
#include <algorithm> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cstring> typedef long long ll; #define clr(a) memset((a),0,sizeof (a)) #define rep(i,a,b) for(int i=(a);i<(int)(b);i++) #define per(i,a,b) for(int i=((a)-1);i>=(int)(b);i--) #define inf 0x7ffffff #define eps 1e-6 using namespace std; int n,m; int a[200005]; int main(){ int n,m; int fu=0,zhen=0; cin>>n>>m; int ai; for(int i=0;i<n;i++){ cin>>ai; if(ai<0) fu++; else zhen++; } int maxn=min(fu,zhen); int p,q; while(m--){ cin>>p>>q; int cnt=q-p+1; if(cnt&1)cout<<0<<endl; else if((cnt/2)>maxn)cout<<0<<endl; else cout<<1<<endl; } //system("pause"); return 0; }