AtCoder Grand Contest 015

Submission #8399435

Source codeソースコード

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100010
#define mod 1000000007
#define ll long long
using namespace std;
ll tree[N<<2];
void insert(int u,int l,int r,int p,int v)
{
	if(l==r){tree[u]=(tree[u]+v)%mod;return;}
	int mid=(l+r)>>1;
	if(p<=mid) insert(u<<1,l,mid,p,v);
	else insert(u<<1|1,mid+1,r,p,v);
	tree[u]=tree[u<<1]+tree[u<<1|1];
}
ll answer(int u,int l,int r,int L,int R)
{
	if(L<=l && r<=R) return tree[u];
	int mid=(l+r)>>1;
	ll ans=0;
	if(L<=mid) ans+=answer(u<<1,l,mid,L,R);
	if(R>mid) ans+=answer(u<<1|1,mid+1,r,L,R);
	return ans%mod;
}
struct node{
	int x,v,id;
	bool operator <(const node a)const{return x<a.x;}
}p[N];
bool cmp(node a,node b){return a.v<b.v;}
struct ques{
	int l,r;
	bool operator <(const ques a)const{return r==a.r?l<a.l:r<a.r;}
}q[N];
int l[N],r[N],f[N];
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].v);
	
	sort(p+1,p+n+1,cmp);
	for(int i=1;i<=n;i++)p[i].id=i;
	sort(p+1,p+n+1);
	int res=n+1;
	for(int i=n;i;i--)
	{
		res=min(res,p[i].id);
		q[p[i].id].l=res;
	}
	res=0;
	for(int i=1;i<=n;i++)
	{
		res=max(res,p[i].id);
		q[p[i].id].r=res;
	}
	sort(q+1,q+n+1);
	ll ans=0;
	for(int i=1;i<=n;i++)
	{
		int p=q[i].l==1;
		(p+=answer(1,1,n,max(q[i].l-1,1),q[i].r))%=mod;
		insert(1,1,n,q[i].r,p);
		if(q[i].r==n) (ans+=p)%=mod;
	}
	printf("%lld",ans);
	return 0;
}

Submission

Task問題 E - Mr.Aoki Incubator
User nameユーザ名 Flying2018
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 RE
Score得点 0
Source lengthソースコード長 1451 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Compiler messageコンパイルメッセージ

./Main.cpp: In function ‘int main()’:
./Main.cpp:40:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:41:53: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].v);
^

Test case

Set

Set name Score得点 / Max score Cases
Sample - s1.txt,s2.txt
All 0 / 1200 01.txt,02.txt,03.txt,04.txt,05.txt,06.txt,07.txt,08.txt,09.txt,10.txt,11.txt,12.txt,13.txt,14.txt,15.txt,16.txt,17.txt,18.txt,19.txt,20.txt,21.txt,22.txt,23.txt,24.txt,25.txt,26.txt,27.txt,28.txt,29.txt,30.txt,31.txt,32.txt,33.txt,34.txt,s1.txt,s2.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01.txt RE
02.txt RE
03.txt RE
04.txt RE
05.txt RE
06.txt RE
07.txt RE
08.txt RE
09.txt RE
10.txt RE
11.txt RE
12.txt RE
13.txt RE
14.txt RE
15.txt RE
16.txt RE
17.txt RE
18.txt RE
19.txt RE
20.txt RE
21.txt RE
22.txt RE
23.txt RE
24.txt RE
25.txt RE
26.txt RE
27.txt RE
28.txt RE
29.txt RE
30.txt RE
31.txt AC 2 ms 2304 KB
32.txt AC 2 ms 2304 KB
33.txt AC 2 ms 2304 KB
34.txt AC 2 ms 2304 KB
s1.txt AC 2 ms 2304 KB
s2.txt AC 2 ms 2304 KB