Submission #62805668

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <vector>
#include <queue>
#include <cstdlib>
#include <cstring>
#include <cstdint>
#include <functional>
#include <stack>
#include <map>
#include <random>
#include <ctime>
#include <unordered_set>
#include <unordered_map>
#include <set>
#include <map>
typedef long long LL;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <vector>
#include <queue>
#include <cstdlib>
#include <cstring>
#include <cstdint>
#include <functional>
#include <stack>
#include <map>
#include <random>
#include <ctime>
#include <unordered_set>
#include <unordered_map>
#include <set>
#include <map>

typedef long long LL;
typedef std::pair<int,int> PII;
typedef std::pair<LL,LL> PLL;

#define INF 0x3f3f3f3f
#define rep(i,l,r) for(auto i(l);i<=(r);++i)
#define per(i,r,l) for(auto i(r);i>=(l);--i)
#define rpp(i,l,r) for(auto i(l);i<(r);++i)
#define ppr(i,r,l) for(auto i(r);i>(l);--i)
#define lowbit(x) ((x)&-(x))
#define ls(p) ((p)<<1)
#define rs(p) ((p)<<1|1)

template<typename T>inline T min(T a,T b){return a<b?a:b;}
template<typename T>inline T max(T a,T b){return a>b?a:b;}
const int N = 200010;
const int M = 5000010;
const int mod = 1'000'000'007;

// char *p1,*p2,buf[100000];
// #define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
template<typename T>inline void read(T &x){
	x=0;
	char ch=getchar(),f=0;
	while(ch<'0' || ch>'9'){f=(ch=='-');ch=getchar();if(ch==EOF){break;}}
	while(ch<='9' && ch>='0'){x=x*10+(ch^48);ch=getchar();}
	f?x=-x:0;
}
template<std::size_t N>inline void read(char (&s)[N]){
	char *p=s,ch=getchar();
	while(isspace(ch)){ch=getchar();if(ch==EOF){break;}}
	while(!isspace(ch) && std::size_t(p-s+1)<N){*p=ch;++p;ch=getchar();}
	while(*p && std::size_t(p-s)<N){*p=0;++p;}
}
inline void read(char &ch){ch=getchar();while(isspace(ch)){ch=getchar();if(ch==EOF){break;}}}
template<typename T,typename... Args>inline void read(T &x,Args&... args){read(x);read(args...);}
template<typename T>inline void write(T x){
	char s[40],*t=s;
	for(;1;++t,x/=10){
		if(x<0){putchar('-');x=-x;}
		if(x<10){*t=x^48;break;}
		*t=(x%10)^48;
	}
	while(t>=s){putchar(*t);--t;}
}
inline void write(char *s){while(*s){putchar(*s);++s;}}
inline void write(const char *s){while(*s){putchar(*s);++s;}}
inline void write(char ch){putchar(ch);}
template<typename T,typename... Args>void write(T x,Args ...args){write(x);write(args...);}
template<typename T>inline void writen(T x){write(x,'\n');}
template<typename T,typename... Args>void writen(T x,Args ...args){write(x,'\n');writen(args...);}
template<typename T>inline void writel(T x){write(x,'\n');}
template<typename T,typename... Args>void writel(T x,Args ...args){write(x,' ');writel(args...);}

int n,q;
int a[N];
int t[N];
int ans[N];

struct node{
	int r,x,id;
};

std::vector<node> v;
std::vector<PII> p;

auto update = [](int x,int d){
	while(x<=n){
		t[x]=max(t[x],d);
		x+=lowbit(x);
	}
};

auto sum = [](int x){
	int res=0;
	while(x){
		res=max(res,t[x]);
		x-=lowbit(x);
	}
	return res;
};

int main(){
	read(n,q);
	rep(i,1,n){read(a[i]);p.push_back({a[i],i});}	
	rep(i,1,q){
		node t;
		read(t.r,t.x);
		t.id=i;
		v.emplace_back(t);
	}

	std::sort(v.begin(),v.end(),[](node a,node b){return a.x<b.x;});
	std::sort(p.begin(),p.end(),[](PII a,PII b){return a.first>b.first || (a.first==b.first && a.second<b.second);});
	for(auto i : v){
		while(!p.empty() && p.back().first<=i.x){
			auto x=p.back();p.pop_back();
			update(x.second,sum(x.second)+1);
		}
		ans[i.id]=sum(i.r);
	}
	rep(i,1,q){writen(ans[i]);}

	return 0;
}
/*
-std=c++14
-Wall -O2 -static
-Wall -O2 -fsanitize=address,undefined
LHY qingchunkeai,shanliangdafang,wengrouxianhui,meilidongren,chenyuluoyan,biyuexiuhua
*/

Submission Info

Judge Result