AtCoder Grand Contest 015

Submission #8399459

Source codeソースコード

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 400010
#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状態 WA
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 AC 132 ms 12544 KB
02.txt WA
03.txt WA
04.txt AC 141 ms 12544 KB
05.txt WA
06.txt WA
07.txt WA
08.txt AC 110 ms 10496 KB
09.txt AC 123 ms 12544 KB
10.txt AC 78 ms 10496 KB
11.txt AC 110 ms 12544 KB
12.txt AC 122 ms 12544 KB
13.txt AC 110 ms 12544 KB
14.txt AC 113 ms 12544 KB
15.txt AC 122 ms 12544 KB
16.txt AC 111 ms 12544 KB
17.txt AC 113 ms 12544 KB
18.txt AC 123 ms 12544 KB
19.txt AC 110 ms 12544 KB
20.txt AC 113 ms 12544 KB
21.txt AC 125 ms 12544 KB
22.txt AC 115 ms 12544 KB
23.txt AC 116 ms 12544 KB
24.txt AC 125 ms 12544 KB
25.txt AC 123 ms 12544 KB
26.txt AC 126 ms 12544 KB
27.txt AC 135 ms 12544 KB
28.txt AC 127 ms 12544 KB
29.txt AC 119 ms 12544 KB
30.txt AC 128 ms 12544 KB
31.txt AC 2 ms 6400 KB
32.txt AC 2 ms 6400 KB
33.txt AC 2 ms 6400 KB
34.txt AC 2 ms 6400 KB
s1.txt AC 2 ms 6400 KB
s2.txt AC 2 ms 6400 KB