wangyj

wangyj
6天前
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n,m,a[300005],s[300005];
vector<int>alls;
int find(int x)
{
int l=0,r=alls.size()-1,mid;
while(l<r){
mid=(l+r)>>1;
if(alls[mid]>=x)r=mid;
else l=mid+1;
}
return r+1;
}
vector<int>::iterator unique(vector<int>&a)
{
int j=0,i;
for (i=0;i<a.size();i++)
if(!i||a[i]!=a[i-1])a[j++]=a[i];
return a.begin()+j;
}
int main()
{
int i,l,r,x,c;
cin>>n>>m;
for(i=0;i<n;i++){
cin>>x>>c;
alls.push_back(x);
}
for(i=0;i<m;i++){
cin>>l>>r;
query.push_back({l,r});
alls.push_back(l);
alls.push_back(r);
}
sort(alls.begin(), alls.end());
alls.erase(unique(alls), alls.end());
x=find(item.first);
a[x]+=item.second;
}
for(i=1;i<=alls.size();i++)s[i]=s[i-1]+a[i];
for(auto item:query){
l=find(item.first),r=find(item.second);
cout<<s[r]-s[l-1]<<endl;
}
return 0;
}


wangyj
6天前

# 803. 区间合并

## 题目描述

1≤n≤100000,
−10^9≤li≤ri≤10^9

#### 样例

输入样例：
5
1 2
2 4
5 6
7 8
7 9

3


# include[HTML_REMOVED]

using namespace std;
vector[HTML_REMOVED] > sect,newsec;
main()
{
int n,i,l,r,l1,r1;
scanf(“%d”,&n);
for(i=0;i[HTML_REMOVED] > ::iterator iter;
for(iter=sect.begin();iter!=sect.end();iter){
if(r1<(*iter).first){
// newsec.push_back({l1,r1}); // if use { } g
complier will warning
newsec.push_back(make_pair(l1,r1));
l1=(iter).first;
r1=(
iter).second;
}
else{
if(r1<(iter).second)r1=(iter).second;
}
}
newsec.push_back(make_pair(l1,r1));
printf(“%d\n”,newsec.size());
return 0;
}


wangyj
6天前

# 803. 区间合并

1≤n≤100000,
−109≤li≤ri≤109

5
1 2
2 4
5 6
7 8
7 9

3

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<pair<int,int> > sect,newsec;
main()
{
int n,i,l,r,l1,r1;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d %d",&l,&r);
sect.push_back(make_pair(l,r));
}
sort(sect.begin(),sect.end());
l1=(*sect.begin()).first;
r1=(*sect.begin()).second;
vector<pair<int,int> > ::iterator iter;
for(iter=sect.begin();iter!=sect.end();iter++){
if(r1<(*iter).first){
//          newsec.push_back({l1,r1});      // if use { } g++ complier will warning
newsec.push_back(make_pair(l1,r1));
l1=(*iter).first;
r1=(*iter).second;
}
else{
if(r1<(*iter).second)r1=(*iter).second;
}
}
newsec.push_back(make_pair(l1,r1));
printf("%d\n",newsec.size());
return 0;
}


wangyj
8天前
1. 数组元素的目标和
给定两个升序排序的有序数组A和B，以及一个目标值x。数组下标从0开始。
请你求出满足A[i] + B[j] = x的数对(i, j)。
数据保证有唯一解。
输入格式
第一行包含三个整数n，m，x，分别表示A的长度，B的长度以及目标值x。
第二行包含n个整数，表示数组A。
第三行包含m个整数，表示数组B。
输出格式
共一行，包含两个整数 i 和 j。
数据范围
数组长度不超过100000。
同一数组内元素各不相同。
1≤数组元素≤109
输入样例：
4 5 6
1 2 4 7
3 4 6 8 9
输出样例：
1 1
#include<cstdio>
using namespace std;
int a[100005],b[100005];
int main()
{
int n,m,x,i,j;
scanf("%d%d%d",&n,&m,&x);
for(i=0;i<n;i++)scanf("%d",&a[i]);
for(i=0;i<m;i++)scanf("%d",&b[i]);
for(i=0,j=m-1;i<n;i++){
while(j>=0&&a[i]+b[j]>x)j--;
if(a[i]+b[j]==x){
printf("%d %d\n",i,j);
return 0;
}
}
}


wangyj
8天前
1. 数组元素的目标和
给定两个升序排序的有序数组A和B，以及一个目标值x。数组下标从0开始。
请你求出满足A[i] + B[j] = x的数对(i, j)。
数据保证有唯一解。
输入格式
第一行包含三个整数n，m，x，分别表示A的长度，B的长度以及目标值x。
第二行包含n个整数，表示数组A。
第三行包含m个整数，表示数组B。
输出格式
共一行，包含两个整数 i 和 j。
数据范围
数组长度不超过100000。
同一数组内元素各不相同。
1≤数组元素≤109
输入样例：
4 5 6
1 2 4 7
3 4 6 8 9
输出样例：
1 1
#include<cstdio>
using namespace std;
int a[100005],b[100005];
int main()
{
int n,m,x,i,j;
scanf("%d%d%d",&n,&m,&x);
for(i=0;i<n;i++)scanf("%d",&a[i]);
for(i=0;i<m;i++)scanf("%d",&b[i]);
for(i=0,j=m-1;i<n;i++){
while(j>=0&&a[i]+b[j]>x)j--;
if(a[i]+b[j]==x){
printf("%d %d\n",i,j);
return 0;
}
}
}


wangyj
12天前

# 801. 二进制中1的个数

1≤n≤100000,
0≤数列中元素的值≤109

5
1 2 3 4 5

1 1 2 1 2

## 程序：

#include<cstdio>
using namespace std;
int lowbits(int m)
{
return -m&m;
}
int main()
{
int n,m,sum;
scanf("%d",&n);
while(n--){
scanf("%d",&m);
sum=0;
while(m){
m-=lowbits(m);
sum++;
}
printf("%d ",sum);
}
printf("\n");
return 0;
}


wangyj
12天前

# 801. 二进制中1的个数

1≤n≤100000,
0≤数列中元素的值≤109

5
1 2 3 4 5

1 1 2 1 2

## 程序：

#include<cstdio>
using namespace std;
int lowbits(int m)
{
return -m&m;
}
int main()
{
int n,m,sum;
scanf("%d",&n);
while(n--){
scanf("%d",&m);
sum=0;
while(m){
m-=lowbits(m);
sum++;
}
printf("%d ",sum);
}
printf("\n");
return 0;
}


wangyj
12天前

# 799. 最长连续不重复子序列

1≤n≤100000

## 样例：

5
1 2 2 3 5

3

### 程序：

#include<iostream>
using namespace std;
int a[100005],s[100005];
int main()
{
int n,sum=0,i,j;
scanf("%d",&n);
for(i=0;i<n;i++)scanf("%d",&a[i]);
for(i=0,j=0;i<n;i++){
s[a[i]]++;
while(j<=i&&s[a[i]]>1){s[a[j]]--,j++;}
sum=max(sum,i-j+1);
}
printf("%d\n",sum);
return 0;
}


wangyj
12天前

# 799. 最长连续不重复子序列

1≤n≤100000

## 样例：

5
1 2 2 3 5

3

### 程序：

#include<iostream>
using namespace std;
int a[100005],s[100005];
int main()
{
int n,sum=0,i,j;
scanf("%d",&n);
for(i=0;i<n;i++)scanf("%d",&a[i]);
for(i=0,j=0;i<n;i++){
s[a[i]]++;
while(j<=i&&s[a[i]]>1){s[a[j]]--,j++;}
sum=max(sum,i-j+1);
}
printf("%d\n",sum);
return 0;
}


wangyj
13天前

# 786. 第k个数

1≤n≤100000,
1≤k≤n

5 3
2 4 1 5 3

3

## 程序：

#include<cstdio>
#include<algorithm>
using namespace std;
int a[1000005],i,j,n,x,m;
void quick_sort(int a[],int down,int up)
{
if(down>=up)return;
i=down-1,j=up+1,x=a[(down+up)/2];
while(i<j){
do i++;while(a[i]<x);
do j--;while(a[j]>x);
if(i<j)swap(a[i],a[j]);
}
quick_sort(a,down,j);
quick_sort(a,j+1,up);
}

int main()
{
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)scanf("%d",&a[i]);
quick_sort(a,0,n-1);
printf("%d\n",a[m-1]);
return 0;
}
`