DreamChaser

$n,q\le 100000$

(其实之前发过一个帖子，只是大家似乎都没有回答…)

#include <iostream>
#include <algorithm>

using namespace std;
const int N=3000000;

int n,q,a[N];
int l,r;

int main() {
cin>>n>>q;
for(int i=1; i<=n; i++) cin>>a[i];
while(q--) {
cin>>l>>r;
bool ok=true;
for(int i=l; i<r; i++) if(abs(a[i+1]-a[i])>1) ok=false;
if(ok) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}


#include<bits/stdc++.h>
#define ll long long
#define landingyu work();
#define AK return
#define IOI 0;
#define inf 0x3f3f3f3f
#define eps 0.00001
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
int F[1000];
void write(int x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9)write(x/10);
putchar(x%10+'0');
}
using namespace std;
int a[100010],ans;
void work(){
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
for(int i=1;i<=n;i++) ans+=abs(a[i]-a[n+1>>1]);
cout<<ans;
}
int main(){landingyu AK IOI}



#include<bits/stdc++.h>
using namespace std;
int n,m,ans0=1,ans1,ans2,tot,k;
int a[200010],x[200010],y[200010],cinema[600010],ans[600010];
int find(int f){
return lower_bound(cinema+1,cinema+k+1,f)-cinema;
}
int main(){
cin>>n;
for(int i=1; i<=n; i++) {
cin>>a[i];
cinema[++tot]=a[i];
}
cin>>m;
for(int i=1; i<=m; i++) {
cin>>x[i];
cinema[++tot]=x[i];
}
for (int i=1; i<=m; i++) {
cin>>y[i];
cinema[++tot]=y[i];
}
sort(cinema+1,cinema+tot+1);
k=unique(cinema+1,cinema+tot+1)-(cinema+1);
for(int i=1; i<=n; i++) ans[find(a[i])]++;
for(int i=1; i<=m; i++) {
int ansx=ans[find(x[i])],ansy=ans[find(y[i])];
if(ansx>ans1 || (ansx==ans1 && ansy>ans2)) {
ans0=i;
ans1=ansx;
ans2=ansy;
}
}
cout<<ans0;
return 0;
}


// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<int> specialSort(int n) {
vector<int> res;
res.push_back(1);
for(int i=2;i<=n;i++){
int l=0,r=res.size()-1;
while(l<r){
int mid=(l+r+1)>>1;
if(compare(res[mid],i)) l=mid;
else r=mid-1;
}
res.push_back(i);
for(int j=res.size()-2;j>=r+1;j--) swap(res[j],res[j+1]);
if(compare(i,res[r])) swap(res[r],res[r+1]);
}
return res;
}
};


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
double a[100001],b[100001],sum[100001];
int main(){
int N,L;
cin>>N>>L;
for(int i=1;i<=N;i++) scanf("%lf",&a[i]);
double eps=1e-5;
double l=-1e6,r=1e6;
while(r-l>eps){
double mid=(l+r)/2;
for(int i=1;i<=N;i++) b[i]=a[i]-mid;
for(int i=1;i<=N;i++) sum[i]=(sum[i-1]+b[i]);
double ans=-1e10;
double min_val=1e10;
for(int i=L;i<=N;i++){
min_val=min(min_val,sum[i-L]);
ans=max(ans,sum[i]-min_val);
}
if(ans>=0) l=mid;
else r=mid;
}
cout<<int(r*1000)<<endl;
return 0;
}



#include<bits/stdc++.h>
#define ll long long
#define landingyu work();
#define AK return
#define IOI 0;
#define inf 0x3f3f3f3f
#define eps 0.00001
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
int F[1000];
void write(int x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9)write(x/10);
putchar(x%10+'0');
}
using namespace std;
map<pair<int,int>,bool> existed;
int c[10010],d[10010];
void work(){
for(int i=1;i<=m;i++){
if(a>b) swap(a,b);
if(existed[make_pair(a,b)]) continue;
d[a+1]--,d[b]++;
existed[make_pair(a,b)]=true;
}
for(int i=1;i<=n;i++){
c[i]=c[i-1]+d[i];
cout<<c[i]+h<<endl;
}
}
int main(){landingyu AK IOI}



#include<bits/stdc++.h>
#define ll long long
#define landingyu work();
#define AK return
#define IOI 0;
#define inf 0x3f3f3f3f
#define eps 0.00001
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
int F[1000];
void write(int x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9)write(x/10);
putchar(x%10+'0');
}
using namespace std;
int a[100010],b[100010];
void work(){
for(int i=1;i<=n;i++) b[i]=a[i]-a[i-1];
b[n+1]=0;
long long p=0,q=0;
for(int i=2;i<=n;i++) {
if(b[i]>0) p+=b[i];
if(b[i]<0) q-=b[i];
}
cout<<max(p,q)<<endl<<abs(p-q)+1;
}
int main(){landingyu AK IOI}


#include<bits/stdc++.h>
using namespace std;
int a[5010][5010];
int x,y,w;
int ans;
int main(){
int n,r;
cin>>n>>r;
for(int i=1; i<=n; i++) {
cin>>x>>y>>w;
a[x+1][y+1]=w;
}
for(int i=1; i<=5001; i++)
for(int j=1; j<=5001; j++)
a[i][j]=a[i-1][j]+a[i][j-1]+a[i][j]-a[i-1][j-1];
for(int i=0; i<5001-r; i++)
for(int j=0; j<5001-r; j++)
ans=max(ans,a[i+r][j+r]-a[i+r][j]-a[i][j+r]+a[i][j]);
cout<<ans;
return 0;
}



#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define ll long long
#define landingyu work();
#define AK return
#define IOI 0;
#define inf 0x3f3f3f3f
#define eps 0.00001
long long x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
int F[1000];
void write(int x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9)write(x/10);
putchar(x%10+'0');
}
using namespace std;
int N;
long long S,D;
pair<long long,long long> calc(int n,long long m){
if(n==0) return make_pair(0,0);
long long len=1ll<<(n-1),cnt=1ll<<(2*n-2);
auto pos=calc(n-1,m%cnt);
auto x=pos.first,y=pos.second;
auto z=m/cnt;
if(z==0) return make_pair(y,x);
if(z==1) return make_pair(x,y+len);
if(z==2) return make_pair(x+len,y+len);
if(z==3) return make_pair(2*len-y-1,len-x-1);
}
void work(){