Submission #1205003


Source Code Expand

#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
ostream &operator<<(ostream &os, const pint &a) { os << "(" << a.fi << "," << a.se << ")"; return os; }
ostream &operator<<(ostream &os, const vector<int> &a) {
	os<<"[";
	rep(i,a.size()){
		os<<a[i];
		if(i<a.size()-1) os<<",";
	}
	os<<"]";
	return os; 
}
#define maxv 5141919
vector<int> gr[maxv],rgr[maxv];
vector<int> vs;
bool sumi[maxv];
int cmp[maxv];
void dfs(int v){
	sumi[v]=true;
	rep(i,gr[v].size()){
		if(!sumi[gr[v][i]]) dfs(gr[v][i]);
	}
	vs.pb(v);
}
void rdfs(int v,int k){
	sumi[v]=true;cmp[v]=k;
	rep(i,rgr[v].size()){
		if(!sumi[rgr[v][i]]) rdfs(rgr[v][i],k);
	}
}
int scc(int v)
{
	memset(sumi,false,sizeof(sumi));
	vs.clear();
	rep(i,v){
		if(!sumi[i]) dfs(i);
	}
	memset(sumi,false,sizeof(sumi));
	int k=0;
	for(int i=vs.size()-1;i>=0;i--){
		if(!sumi[vs[i]]) rdfs(vs[i],k++);
	}
	return k;
}

void aedge(int v,int w){
	//cout<<v<<' '<<w<<endl;
	gr[v].pb(w);
	rgr[w].pb(v);
}
#define N 65536
int act[2][N*2+10];
//[a,b)にvから辺を貼る
void query(int a,int b,int v,int id,int k=0,int l=0,int r=N){
	if(r<=a || b<=l) return;
	if(a<=l && r<=b){
		aedge(v,act[id][k]);return;
	}
	query(a,b,v,id,k*2+1,l,(l+r)/2);
	query(a,b,v,id,k*2+2,(l+r)/2,r);
}
int n;
//(id,x)に点yを貼る
void ap(int id,int x,int y){
	int k=x+N-1,pre=y;
	while(1){
		int np=n;n++;
		aedge(np,pre);
		aedge(np,act[id][k]);
		act[id][k]=np;
		pre=act[id][k];
		if(k<1) break;
		k=(k-1)/2;
	}
}
int l[51419],r[51419];
int pos[2][51419];
vector<pint> V[2];
int num[maxv],dp[maxv];
vector<int> ed[maxv];
int cal(int v){
	if(dp[v]>=0) return dp[v];
	int ret=0;
	rep(i,ed[v].size()){
		if(v!=ed[v][i]) ret=max(ret,cal((ed[v][i])));
	}
	return dp[v]=ret+num[v];
}
int main()
{
	int m;
	cin>>m;
	rep(i,m) cin>>l[i];
	rep(i,m) cin>>r[i];
	rep(i,m) V[0].pb(mp(l[i]-i,i)),V[1].pb(mp(l[i]+i,i));
	V[0].pb(mp(1145141919,1145141919));V[1].pb(mp(1145141919,1145141919));
	sort(All(V[0]));sort(All(V[1]));
	rep(i,2) rep(j,m) pos[i][V[i][j].se]=j;
	
	n=m;
	rep(i,N*2-1){act[0][i]=n;n++;}
	rep(i,N*2-1){act[1][i]=n;n++;}
	REP(i,1,N*2-1) aedge(act[0][(i-1)/2],act[0][i]),aedge(act[1][(i-1)/2],act[1][i]);
	rep(i,m){
		query(0,lower_bound(All(V[0]),mp(r[i]-i,114514))-V[0].begin(),i,0);
		ap(0,pos[0][i],i);
	}
	for(int i=m-1;i>=0;i--){
		query(1,lower_bound(All(V[1]),mp(r[i]+i,114514))-V[1].begin(),i,1);
		ap(1,pos[1][i],i);
	}
	
	int v=scc(n),out=0;
	memset(num,0,sizeof(num));memset(dp,-1,sizeof(dp));
	rep(i,m) num[cmp[i]]++;
	rep(i,n) rep(j,gr[i].size()) ed[cmp[i]].pb(cmp[gr[i][j]]);
	rep(i,v){
		if(ed[i].size()>0){
			sort(All(ed[i]));
			ed[i].erase(unique(All(ed[i])),ed[i].end());
		}
	}
	rep(i,v) out=max(out,cal(i));
	cout<<out<<endl;
}

Submission Info

Submission Time
Task E - 遊園地
User sky58
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3467 Byte
Status WA
Exec Time 1739 ms
Memory 632716 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1200
Status
AC × 3
AC × 27
WA × 9
Set Name Test Cases
Sample sample1.txt, sample2.txt, sample3.txt
All in1.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in2.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in29.txt, in3.txt, in30.txt, in31.txt, in32.txt, in33.txt, in4.txt, in5.txt, in6.txt, in7.txt, in8.txt, in9.txt, sample1.txt, sample2.txt, sample3.txt
Case Name Status Exec Time Memory
in1.txt AC 1674 ms 632716 KB
in10.txt WA 1662 ms 631176 KB
in11.txt AC 1398 ms 617184 KB
in12.txt WA 1324 ms 617184 KB
in13.txt AC 1296 ms 619104 KB
in14.txt WA 1298 ms 618592 KB
in15.txt AC 1386 ms 616544 KB
in16.txt AC 1453 ms 615904 KB
in17.txt WA 1467 ms 615904 KB
in18.txt WA 1517 ms 614472 KB
in19.txt AC 1516 ms 614600 KB
in2.txt AC 1666 ms 631436 KB
in20.txt WA 1480 ms 614752 KB
in21.txt AC 1286 ms 621284 KB
in22.txt AC 1215 ms 623204 KB
in23.txt AC 1279 ms 625380 KB
in24.txt AC 1270 ms 624996 KB
in25.txt AC 1274 ms 621412 KB
in26.txt AC 201 ms 427892 KB
in27.txt AC 198 ms 427892 KB
in28.txt AC 200 ms 427892 KB
in29.txt AC 1642 ms 632416 KB
in3.txt AC 1658 ms 632456 KB
in30.txt AC 1732 ms 632544 KB
in31.txt AC 1739 ms 631776 KB
in32.txt AC 1726 ms 632032 KB
in33.txt WA 1723 ms 632160 KB
in4.txt WA 1692 ms 631820 KB
in5.txt AC 1645 ms 632712 KB
in6.txt AC 1650 ms 632460 KB
in7.txt AC 1561 ms 631432 KB
in8.txt WA 1656 ms 631944 KB
in9.txt AC 1574 ms 632680 KB
sample1.txt AC 199 ms 427892 KB
sample2.txt AC 199 ms 427892 KB
sample3.txt AC 200 ms 427892 KB