QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#18940 | #1877. Matryoshka Dolls | Jake | Compile Error | / | / | C | 2.8kb | 2022-01-27 16:12:12 | 2022-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]
- 评测
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [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.