QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#18940#1877. Matryoshka DollsJakeCompile Error//C2.8kb2022-01-27 16:12:122022-05-18 04:05:25

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-18 04:05:25]
  • 评测
  • [2022-01-27 16:12:12]
  • 提交

answer

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<set>
using namespace std;
int Read()
{
	char c=getchar();
	while (c<'0'||c>'9') c=getchar();
	int t=c-'0'; c=getchar();
	while (c>='0'&&c<='9') t=(t<<3)+(t<<1)+c-'0',c=getchar();
	return t;
}
#define ll long long
int n,m;
int a[500001];
struct Node
{
	int l,r,bh;
}b[500001];
int rk[500001];
set <int> s;
set <int> ::iterator it;
ll ans[1005][1005],ans2[500001];
int T;
bool cmp(const Node& t1,const Node& t2)
{
	if (t1.l/T!=t2.l/T) return t1.l<t2.l;
	else return t1.r<t2.r;
}
ll sum;
void add(int j)
{
	it=s.lower_bound(a[j]);
	int m1=0,m2=0;
	if (it!=s.end()&&it!=s.begin())
	{
		m2=*it; m2=rk[m2];
		it--;
		m1=*it; m1=rk[m1];
		sum=sum-abs(m1-m2)+abs(j-m1)+abs(j-m2);
	}
	else if (it==s.end()&&it!=s.begin())
	{
		it--;
		m1=*it; m1=rk[m1];
		sum=sum+abs(j-m1);
	}
	else if (it==s.begin()&&it!=s.end())
	{
		m2=*it; m2=rk[m2];
		sum=sum+abs(j-m2);
	}
	else
	{
		
	}
	s.insert(a[j]);
}
void del(int j)
{
	s.erase(a[j]);
	it=s.lower_bound(a[j]);
	int m1=0,m2=0;
	if (it!=s.end()&&it!=s.begin())
	{
		m2=*it; m2=rk[m2];
		it--;
		m1=*it; m1=rk[m1];
		sum=sum+abs(m1-m2)-abs(j-m1)-abs(j-m2);
	}
	else if (it==s.end()&&it!=s.begin())
	{
		it--;
		m1=*it; m1=rk[m1];
		sum=sum-abs(j-m1);
	}
	else if (it==s.begin()&&it!=s.end())
	{
		m2=*it; m2=rk[m2];
		sum=sum-abs(j-m2);
	}
	else
	{
		
	}
}
int main()
{
	//freopen("rrads.in","r",stdin);
	//freopen("rrads.out","w",stdout);
	
	n=Read(); m=Read();
	for (int i=1;i<=n;i++) a[i]=Read(),rk[a[i]]=i;
	for (int i=1;i<=m;i++)
	{
		b[i].l=Read(),b[i].r=Read();
		b[i].bh=i;
	}
	if (n<=1001)
	{
		for (int i=1;i<=n;i++)
		{
			ll sum=0;
			s.clear();
			ans[i][i]=0;
			s.insert(a[i]);
			for (int j=i+1;j<=n;j++)
			{
				it=s.lower_bound(a[j]);
				int m1=0,m2=0;
				if (it!=s.end()&&it!=s.begin())
				{
					m2=*it; m2=rk[m2];
					it--;
					m1=*it; m1=rk[m1];
					sum=sum-abs(m1-m2)+abs(j-m1)+abs(j-m2);
				}
				else if (it==s.end())
				{
					it--;
					m1=*it; m1=rk[m1];
					sum=sum+abs(j-m1);
				}
				else if (it==s.begin())
				{
					m2=*it; m2=rk[m2];
					sum=sum+abs(j-m2);
				}
				s.insert(a[j]);
				ans[i][j]=sum;
			}
		}
		for (int i=1;i<=m;i++)
		{
			printf("%lld\n",ans[b[i].l][b[i].r]);
		}
	}
	else
	{
		T=sqrt(m);
		if (T==0) T=1;
		sort(b+1,b+m+1,cmp);
		int l=1,r=0;
		for (int i=1;i<=m;i++)
		{
			while (r<b[i].r)
			{
				r++;
				add(r);
			}
			while (l>b[i].l)
			{
				l--;
				add(l);
			}
			while (r>b[i].r)
			{
				del(r);
				r--;
			}
			while (l<b[i].l)
			{
				del(l);
				l++;
			}
			ans2[b[i].bh]=sum;
		}
		for (int i=1;i<=m;i++) printf("%lld\n",ans2[i]);
	}
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}

Details

answer.code:1:9: fatal error: cstdio: No such file or directory
 #include<cstdio>
         ^~~~~~~~
compilation terminated.