A. 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
题目很简单，看懂题意就能AC
题意：给你一个N个整数数列 a1, a2, ..., an (ai = -1, 1)，它的元素只有1和-1，然后给你m询问，每个询问包含两个整数li, ri (1 ≤ li ≤ ri ≤ n)，如果从ali + ali + 1 + ... + ari = 0就输出1否则就输出0，记住整个数列可以重新排列，例如第二个测试用例那个“2
3”本来从原来的排列来看2 3分别代表a2=1加到a3=1就是1+1=2，可是重排下把a1换到a2位置那就变成了-1+1=0所以输出1，再例如“2 5”，是从a2加到a5就是1+1+1+（-1）=2，可是把a1换到a2位置就变成（-1）+1+1+（-1）=0所以也是输出1，所以综合来看，要使ali + ali + 1 + ... + ari = 0，就看这个数列-1和1的个数能不能大于或等于ari -ali 的一半（1的个数大于或等于ari -ali 的一半还有-1的个数大于或等于ari -ali 的一半）如果是就一定能让数列重排使ali + ali + 1 + ... + ari = 0，当然这里我们还要注意ari -ali 不能为奇数，如果为奇数，不管数列有多少-1和1，都不能使ali + ali + 1 + ... + ari = 0，这个我们可以想象如果ari -ali 为奇数，那么就代表从ali 到ari一定有-1的个数大于1的个数或者1的个数大于-1的个数，再或者全是1或者-1，就不能使其和等于0。
3”本来从原来的排列来看2 3分别代表a2=1加到a3=1就是1+1=2，可是重排下把a1换到a2位置那就变成了-1+1=0所以输出1，再例如“2 5”，是从a2加到a5就是1+1+1+（-1）=2，可是把a1换到a2位置就变成（-1）+1+1+（-1）=0所以也是输出1，所以综合来看，要使ali + ali + 1 + ... + ari = 0，就看这个数列-1和1的个数能不能大于或等于ari -ali 的一半（1的个数大于或等于ari -ali 的一半还有-1的个数大于或等于ari -ali 的一半）如果是就一定能让数列重排使ali + ali + 1 + ... + ari = 0，当然这里我们还要注意ari -ali 不能为奇数，如果为奇数，不管数列有多少-1和1，都不能使ali + ali + 1 + ... + ari = 0，这个我们可以想象如果ari -ali 为奇数，那么就代表从ali 到ari一定有-1的个数大于1的个数或者1的个数大于-1的个数，再或者全是1或者-1，就不能使其和等于0。
下面附上代码：
#include<iostream>
const int MAX=200000;
int s[MAX];
using namespace std;
int main()
{
int n,m,i,j,a,b,sum,c,d,e,p;
cin>>n>>m;
c=0;d=0;
for(i=1;i<=n;i++)
{
cin>>s[i];
if(s[i]<0)
c+=1;
else
d+=1;
}
for(j=1;j<=m;j++)
{
cin>>a>>b;
e=b-a+1;
if(e%2!=0)
{
p=1;
}
else
{
if(c>=e/2)
{
if(d>=e/2)
p=0;
else
p=1;
}
else
p=1;
}
if(p!=0)
cout<<0<<endl;
else
cout<<1<<endl;
}
return 0;
}//如果有问题，或有什么疑惑，可以在评论中提出，小子我看到一定尽力解答
const int MAX=200000;
int s[MAX];
using namespace std;
int main()
{
int n,m,i,j,a,b,sum,c,d,e,p;
cin>>n>>m;
c=0;d=0;
for(i=1;i<=n;i++)
{
cin>>s[i];
if(s[i]<0)
c+=1;
else
d+=1;
}
for(j=1;j<=m;j++)
{
cin>>a>>b;
e=b-a+1;
if(e%2!=0)
{
p=1;
}
else
{
if(c>=e/2)
{
if(d>=e/2)
p=0;
else
p=1;
}
else
p=1;
}
if(p!=0)
cout<<0<<endl;
else
cout<<1<<endl;
}
return 0;
}//如果有问题，或有什么疑惑，可以在评论中提出，小子我看到一定尽力解答