首页 > 代码库 > Ural 1613-For Fans of Statistics(vector)
Ural 1613-For Fans of Statistics(vector)
1613. For Fans of Statistics
Time limit: 1.0 second
Memory limit: 64 MB
Memory limit: 64 MB
Have you ever thought about how many people are transported by trams every year in a city with a ten-million population where one in three citizens uses tram twice a day?
Assume that there are n cities with trams on the planet Earth. Statisticians counted for each of them the number of people transported by trams during last year. They compiled a table, in which cities were sorted alphabetically. Since city names were inessential for statistics, they were later replaced by numbers from 1 to n. A search engine that works with these data must be able to answer quickly a query of the following type: is there among the cities with numbers from l to r such that the trams of this city transported exactly x people during last year. You must implement this module of the system.
Input
The first line contains the integer n, 0 < n < 70000. The second line contains statistic data in the form of a list of integers separated with a space. In this list, the ith number is the number of people transported by trams of the ith city during last year. All numbers in the list are positive and do not exceed 109 ? 1. In the third line, the number of queries q is given, 0 < q < 70000. The next q lines contain the queries. Each of them is a triple of integers l, r, and x separated with a space; 1 ≤ l ≤ r ≤ n ; 0 < x < 109.
Output
Output a string of length q in which the ith symbol is “1” if the answer to the ith query is affirmative, and “0” otherwise.
Sample
| input | output |
|---|---|
5 1234567 666666 3141593 666666 4343434 5 1 5 3141593 1 5 578202 2 4 666666 4 4 7135610 1 1 1234567 | 10101 |
题意 ：给n个城市的人口数目，城市编号从1到n，然后m次询问，每次给3个数据l r x 问[l,r]闭区间内的城市人口数有没有等于x的，有则输出1，否则输出0；以人口数目为关键字哈希，由于数据太大，普通的数组肯定不行，然后写链表又太麻烦，有一种解决方法是使用动态数组，缺点是效率有点低。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <algorithm>
#include <set>
#include <vector>
#include <string>
#include <map>
#include <queue>
using namespace std;
const int maxn= 300010;
const int mod=299999;
vector <pair<int,int> > p[maxn];
int main()
{
int n,l,r,q,x;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
p[x%mod].push_back(make_pair(i,x));
}
scanf("%d",&q);
while(q--)
{
int flag=1;
scanf("%d%d%d",&l,&r,&x);
int mm=x%mod;
int len=p[mm].size();
for(int i=0;i<len;i++)
{
if(p[mm][i].first>=l&&p[mm][i].first<=r&&p[mm][i].second==x)
{
printf("1");
flag=0;
break;
}
}
if(flag)
printf("0");
}
printf("\n");
return 0;
}
Ural 1613-For Fans of Statistics(vector)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。