AtCoder Grand Contest 015

Submission #1587055

Source codeソースコード

#include<bits/stdc++.h>
#define N 200005
#define LL long long
#define mod 1000000007
using namespace std;
 
struct team{
	int p,v;
	friend bool inline operator < (team a,team b){
		return a.v<b.v;
	}
}Tm[N];
 
struct T_node{
	int l,r;
	LL s,t1,t2;
};
 
struct sg{
	int l,r;
	friend bool inline operator < (sg a,sg b){
		if(a.r==b.r) return a.l<b.l;
		return a.r<b.r;
	}
}a[N];
 
int n,mx[N],mn[N],flag=1;
 
LL inline pw(LL x,LL y){
	LL ret=1,tmp=x;
	while(y){
		if(y&1) ret=ret*tmp%mod;
		y>>=1,tmp=tmp*tmp%mod;
	}
	return ret;
}
 
struct segment_tree{
	T_node p[N<<3];
	void inline pushdown(int x){
		if(p[x].t1==1&&p[x].t2==0) return;
		int T1=p[x].t1,T2=p[x].t2,ls=x<<1,rs=x<<1|1;
		p[x].t1=1,p[x].t2=0;
		(p[ls].s*=T1)%=mod,(p[ls].t1*=T1)%=mod,(p[ls].t2*=T1)%=mod;
		(p[ls].s+=1LL*T2*(p[ls].r-p[ls].l+1))%=mod,(p[ls].t2+=T2)%=mod;
		(p[rs].s*=T1)%=mod,(p[rs].t1*=T1)%=mod,(p[rs].t2*=T1)%=mod;
		(p[rs].s+=1LL*T2*(p[rs].r-p[rs].l+1))%=mod,(p[rs].t2+=T2)%=mod;
	}	
	void inline build(int x,int l,int r){
		p[x].l=l,p[x].r=r,p[x].t1=1;
		if(l==r) return;
		int mid=(l+r)>>1;
		build(x<<1,l,mid),build(x<<1|1,mid+1,r);	
	}
	void inline modify(int x,int l,int r,int opt,int v){
		int L=p[x].l,R=p[x].r;
		pushdown(x);
		if(l==L&&r==R){
			if(opt==2) (p[x].s+=1LL*v*(p[x].r-p[x].l+1))%=mod,(p[x].t2+=v)%=mod;
			else (p[x].s*=v)%=mod,(p[x].t1*=v)%=mod,(p[x].t2*=v)%=mod;
			return;
		}
		int mid=(L+R)>>1;
		if(r<=mid) modify(x<<1,l,r,opt,v);
		else if(l>mid) modify(x<<1|1,l,r,opt,v);
		else modify(x<<1,l,mid,opt,v),modify(x<<1|1,mid+1,r,opt,v);
		p[x].s=p[x<<1].s+p[x<<1|1].s;
	}
	LL inline query(int x,int pos){
		pushdown(x);
		if(p[x].l==p[x].r) return p[x].s;
		int mid=(p[x].l+p[x].r)>>1;
		if(pos<=mid) return query(x<<1,pos);
		return query(x<<1|1,pos);
	}
}T;
 
void inline solve(){
	sort(a+1,a+n+1),T.build(1,1,n);
	for(int i=1;i<=n;i++){
		int l=a[i].l,r=a[i].r;
		if(flag&&l==1) flag=0,T.modify(1,l,r,2,pw(2,i-1));
		else if(!flag){
			LL tmp=(l==1)?pw(2,i-1):T.query(1,l-1);
			T.modify(1,l,r,2,tmp);
			if(l!=1) T.modify(1,1,l-1,1,2);
		}
	}
	printf("%lld\n",T.query(1,n));
}
 
int inline ckmx(int p){
	int l=1,r=p,mid;
	while(l<r){
		mid=(l+r)>>1;
		if(mx[mid]>=Tm[p].p) r=mid;
		else l=mid+1;
	}
	return l;
}
 
int inline ckmn(int p){
	int l=p,r=n,mid;
	while(l+1<r){
		mid=(l+r)>>1;
		if(mn[mid]<=Tm[p].p) l=mid;
		else r=mid-1;
	}
	return (mn[r]<=Tm[p].p)?r:l; 
}
 
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d",&Tm[i].p,&Tm[i].v);
	sort(Tm+1,Tm+n+1),mx[0]=0,mn[n+1]=0x3f3f3f3f;
	for(int i=1;i<=n;i++) mx[i]=max(mx[i-1],Tm[i].p);
	for(int i=n;i;i--) mn[i]=min(mn[i+1],Tm[i].p);
	for(int i=1;i<=n;i++) a[i].l=ckmx(i),a[i].r=ckmn(i);
	
	solve();
}

Submission

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

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

./Main.cpp: In function ‘int main()’:
./Main.cpp:113:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:114:55: 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",&Tm[i].p,&Tm[i].v);
^

Test case

Set

Set name Score得点 / Max score Cases
Sample - s1.txt,s2.txt
All 1200 / 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 227 ms 28288 KB
02.txt AC 181 ms 30336 KB
03.txt AC 160 ms 28288 KB
04.txt AC 295 ms 30336 KB
05.txt AC 140 ms 28288 KB
06.txt AC 190 ms 28288 KB
07.txt AC 209 ms 36480 KB
08.txt AC 154 ms 28288 KB
09.txt AC 199 ms 40576 KB
10.txt AC 84 ms 24192 KB
11.txt AC 194 ms 40576 KB
12.txt AC 202 ms 40576 KB
13.txt AC 190 ms 40576 KB
14.txt AC 191 ms 40576 KB
15.txt AC 201 ms 40576 KB
16.txt AC 190 ms 40576 KB
17.txt AC 189 ms 40576 KB
18.txt AC 199 ms 40576 KB
19.txt AC 188 ms 40576 KB
20.txt AC 189 ms 40576 KB
21.txt AC 222 ms 40576 KB
22.txt AC 214 ms 40576 KB
23.txt AC 214 ms 40576 KB
24.txt AC 222 ms 40576 KB
25.txt AC 268 ms 30336 KB
26.txt AC 273 ms 28288 KB
27.txt AC 268 ms 34432 KB
28.txt AC 282 ms 32384 KB
29.txt AC 232 ms 34432 KB
30.txt AC 228 ms 36480 KB
31.txt AC 1 ms 4352 KB
32.txt AC 1 ms 4352 KB
33.txt AC 1 ms 4352 KB
34.txt AC 1 ms 4352 KB
s1.txt AC 1 ms 4352 KB
s2.txt AC 1 ms 4352 KB