AtCoder Grand Contest 015

Submission #1587052

Source codeソースコード

#include <bits/stdc++.h>
#define mod 1000000007
#define N 400010
using namespace std;
typedef long long ll;
inline int read()
{
	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*10+ch-'0'; ch=getchar();}
	return x*f;
}
inline void pls(int &x,int y)
{
	x+=y; if(x>=mod) x-=mod;
	if(x<0) x+=mod; 
}
int n,L[N],R[N],tree[N<<1];
inline void deal(int x,int y,int tp)
{
	//if(tp==0) cerr << x << " " << y << " " << tp << endl;
	if(tp==1&&tree[x]==0) tree[x]=0x3ffffff;
	if(tp==0) pls(tree[x],y);
	if(tp==1) tree[x]=min(tree[x],y);
	if(tp==2) tree[x]=max(tree[x],y);
	//if(tp==0) cout << tree[x] << endl;
}
inline void qury(int &x,int y,int tp)
{
	if(tp==1&&x==0) x=0x3ffffff;
	if(tp==0) pls(x,y);
	if(tp==1) x=min(x,y);
	if(tp==2) x=max(x,y);
}
inline void add(int x,int y,int tp)
{
	//cout << x << " " << y << " " << tp << " "  << endl;
	for(;x<=n;x+=(x&-x))
		deal(x,y,tp);
}
inline int ask(int x,int tp)
{
	int ret=0; for(;x;x-=(x&-x))
		qury(ret,tree[x],tp); return ret;
}
pair <int,int> Ps[N]; map <int,int> M;
int V[N],Fs[N],rk[N];
inline bool cmp(const int a,const int b)
{
	return (L[a]==L[b])? R[a]<=R[b]:L[a]<L[b];
}
int main()
{
	n=read(); 
	for(int i=1;i<=n;i++)
		Ps[i].second=read(), Ps[i].first=read(),V[++V[0]]=Ps[i].second;
	sort(V+1,V+1+V[0]);
	for(int i=1;i<=V[0];i++) M[V[i]]=i;
	for(int i=1;i<=V[0];i++) Ps[i].second=M[Ps[i].second];
	sort(Ps+1,Ps+1+n);
	for(int i=1;i<=n;i++)
		add(n-Ps[i].second+1,i,1),L[i]=max(1,ask(n-Ps[i].second+1,1));
	memset(tree,0,sizeof tree);
	for(int i=n;i>=1;i--)
		add(Ps[i].second,i,2),R[i]=min(n,ask(Ps[i].second,2));
	memset(tree,0,sizeof tree);
	
	for(int i=1;i<=n;i++) rk[i]=i;
	//for(int i=1;i<=n;i++) printf("%d %d\n",L[rk[i]],R[rk[i]]);
	sort(rk+1,rk+1+n,cmp);
	//for(int i=1;i<=n;i++) printf("%d %d\n",L[rk[i]],R[rk[i]]);
	int ans=0;
	for(int i=n;i>=1;i--)
	{
		if(R[rk[i]]==n) Fs[i]=1;
		Fs[i]+=ask(R[rk[i]],0);
		if(L[rk[i]]==1) pls(ans,Fs[i]);
		add(L[rk[i]],Fs[i],0);
		//cout << Fs[i] << " ";
	}
	//cout <<endl;
	cout << ans << endl;
	return 0;
}

Submission

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

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 TLE
02.txt TLE
03.txt TLE
04.txt TLE
05.txt RE
06.txt RE
07.txt TLE
08.txt TLE
09.txt WA
10.txt RE
11.txt WA
12.txt WA
13.txt WA
14.txt WA
15.txt WA
16.txt WA
17.txt WA
18.txt WA
19.txt WA
20.txt WA
21.txt WA
22.txt WA
23.txt WA
24.txt WA
25.txt TLE
26.txt TLE
27.txt TLE
28.txt TLE
29.txt TLE
30.txt WA
31.txt AC 3 ms 10496 KB
32.txt AC 4 ms 10496 KB
33.txt AC 3 ms 10496 KB
34.txt WA
s1.txt AC 3 ms 10496 KB
s2.txt AC 3 ms 10496 KB