#59771 (C++11) No.284 門松と魔法(2)

提出ソース

結果

問題	No.284 門松と魔法(2)
ユーザー	okuraofvegetabl
提出日時	2015-11-20 20:58:33
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	2,685 ms / 5,000 ms
コード長	4,265 bytes
コンパイル時間	1,178 ms
コンパイル使用メモリ	107,312 KB
実行使用メモリ	16,636 KB
最終ジャッジ日時	2023-10-11 18:10:13
合計ジャッジ時間	19,421 ms
ジャッジサーバーID （参考情報）	judge15 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	8 ms 15,940 KB
testcase_01	AC	8 ms 15,928 KB
testcase_02	AC	8 ms 15,908 KB
testcase_03	AC	7 ms 15,840 KB
testcase_04	AC	7 ms 15,996 KB
testcase_05	AC	8 ms 15,820 KB
testcase_06	AC	8 ms 15,840 KB
testcase_07	AC	8 ms 15,928 KB
testcase_08	AC	9 ms 15,944 KB
testcase_09	AC	7 ms 15,964 KB
testcase_10	AC	11 ms 15,936 KB
testcase_11	AC	10 ms 15,768 KB
testcase_12	AC	11 ms 15,776 KB
testcase_13	AC	8 ms 15,876 KB
testcase_14	AC	9 ms 15,860 KB
testcase_15	AC	8 ms 15,852 KB
testcase_16	AC	11 ms 15,760 KB
testcase_17	AC	9 ms 15,876 KB
testcase_18	AC	11 ms 16,068 KB
testcase_19	AC	9 ms 15,972 KB
testcase_20	AC	9 ms 15,864 KB
testcase_21	AC	10 ms 15,824 KB
testcase_22	AC	13 ms 15,916 KB
testcase_23	AC	149 ms 15,840 KB
testcase_24	AC	1,808 ms 16,280 KB
testcase_25	AC	701 ms 16,028 KB
testcase_26	AC	8 ms 15,964 KB
testcase_27	AC	8 ms 15,860 KB
testcase_28	AC	8 ms 15,940 KB
testcase_29	AC	2,594 ms 16,636 KB
testcase_30	AC	2,149 ms 16,456 KB
testcase_31	AC	935 ms 16,332 KB
testcase_32	AC	2,685 ms 16,480 KB
testcase_33	AC	1,609 ms 16,508 KB
testcase_34	AC	1,588 ms 16,332 KB
testcase_35	AC	8 ms 16,072 KB
testcase_36	AC	8 ms 16,000 KB
testcase_37	AC	1,194 ms 16,340 KB
testcase_38	AC	767 ms 16,260 KB
testcase_39	AC	22 ms 15,864 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <cassert>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define SORT(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++)
#define EQ(a,b) (abs((a)-(b))<eps)
struct Data{
	int len,l,m;
	Data():len(0),l(-1),m(-1){}
	Data(int len,int l,int m):len(len),l(l),m(m){}
};
bool comp(Data a,Data b){
	if(a.len!=b.len)return a.len > b.len;
	if(a.l!=b.l)return a.l > b.l;
	return a.m < b.m;
}
typedef pair<Data,Data> PD;
void print(PD x){
	printf("len %d l %d m %d\n",x.fi.len,x.fi.l,x.fi.m);
	printf("len %d l %d m %d\n",x.sec.len,x.sec.l,x.sec.m);
}
Data input_data(){
	Data res;
	scanf("%d %d %d",&(res.len),&(res.l),&(res.m));
	return res;
}
PD upd(PD a,PD b,int f){
	vector<Data> v;
	v.pb(a.fi);v.pb(a.sec);
	if(b.fi.l!=f)v.pb(Data(b.fi.len+1,b.fi.m,f));
	if(b.fi.len!=0&&b.sec.l!=f)v.pb(Data(b.sec.len+1,b.sec.m,f));
	sort(all(v),comp);
	PD res;
	res.fi = v[0];
	int id = 1;
	while(id<(int)v.size()&&v[id].l==v[0].l)id++;
	res.sec = v[id];
	return res;
}
PD merge(PD a,PD b){
	vector<Data> v;
	v.pb(a.fi);v.pb(a.sec);v.pb(b.fi);v.pb(b.sec);
	sort(all(v),comp);
	PD res;
	res.fi = v[0];
	int id = 1;
	while(id<(int)v.size()&&v[id].l==v[0].l)id++;
	res.sec = v[id];
	return res;
}
const int SIZE = 1<<17;
struct segtree{
	PD seg[SIZE*2];
	segtree(){
		for(int i=0;i<SIZE*2-1;i++)seg[i]=PD(Data(0,-1,-1),Data(0,-2,-2));
	}
	void show(){
		for(int i=SIZE-1;i<SIZE*2-1;i++){
			printf("%d\n",i-SIZE+1);
			print(seg[i]);
		}
	}
	void update(int k,PD x){
		int idx = k+SIZE-1;
		seg[idx]=upd(seg[idx],x,k);
		while(idx){
			idx = (idx-1)/2;
			seg[idx]=merge(seg[idx*2+1],seg[idx*2+2]);
		}
	}
	PD query(int a,int b){
		return query(a,b,0,0,SIZE);
	}
	PD query(int a,int b,int k,int l,int r){
		if(a>=b)return PD(Data(0,-1,-1),Data(0,-2,-2));
		if(r<=a||b<=l)return PD(Data(0,-1,-1),Data(0,-2,-2));
		else if(a<=l&&r<=b)return seg[k];
		else{
			PD lch = query(a,b,k*2+1,l,(l+r)/2);
			PD rch = query(a,b,k*2+2,(l+r)/2,r);
			return merge(lch,rch);
		}
	}
};
segtree up,down;
int N,M,A[100100];
vector<int> vs;
int main(){
	/*while(1){
		PD a,b;
		a.fi = input_data();
		a.sec = input_data();
		b.fi = input_data();
		b.sec = input_data();
		print(merge(a,b));
	}*/
	scanf("%d",&N);
	for(int i=0;i<N;i++){
		scanf("%d",&A[i]);
		vs.pb(A[i]);
	}
	sort(all(vs));
	vs.erase(unique(all(vs)),vs.end());
	M = (int)vs.size();
	for(int i=0;i<N;i++)A[i]=lower_bound(all(vs),A[i])-vs.begin();
	//for(int i=0;i<M;i++)printf("%d%c",vs[i],(i==M-1)?'\n':' ');
	for(int i=0;i<N;i++){
		/*int a;
		scanf("%d",&a);
		printf("down:\n");
		down.show();
		printf("up:\n");
		up.show();*/
		
		PD rd,ri,tmp;
		
		tmp = down.query(0,A[i]);
		if(tmp.fi.l!=A[i])rd.fi=tmp.fi;
		else rd.fi = tmp.sec;
		tmp = down.query(0,rd.fi.m);
		if(tmp.fi.l!=A[i])rd.sec=tmp.fi;
		else rd.sec=tmp.sec;
		tmp = down.query(rd.fi.m+1,A[i]);
		if(tmp.fi.l!=A[i]&&tmp.fi.len>rd.sec.len)rd.sec=tmp.fi;
		if(tmp.sec.l!=A[i]&&tmp.sec.len>rd.sec.len)rd.sec=tmp.sec;
		
		tmp = up.query(A[i]+1,M);
		/*printf("tmp1:\n");
		print(tmp);*/
		if(tmp.fi.l!=A[i])ri.fi=tmp.fi;
		else ri.fi = tmp.sec;
		tmp = up.query(A[i]+1,ri.fi.m);
		/*printf("tmp2:\n");
		print(tmp);*/
		if(tmp.fi.l!=A[i])ri.sec=tmp.fi;
		else ri.sec=tmp.sec;
		tmp = up.query(ri.fi.m+1,M);
		/*printf("tmp3:\n");
		print(tmp);*/
		if(tmp.fi.l!=A[i]&&tmp.fi.len>ri.sec.len)ri.sec=tmp.fi;
		if(tmp.sec.l!=A[i]&&tmp.sec.len>ri.sec.len)ri.sec=tmp.sec;
		
		/*printf("rd:\n");
		print(rd);
		printf("ri:\n");
		print(ri);*/
		up.update(A[i],rd);
		down.update(A[i],ri);
	}
	int ans = (down.query(0,M)).fi.len;
	ans = max(ans,(up.query(0,M)).fi.len);
	if(ans<3)ans = 0;
	printf("%d\n",ans);
	return 0;
}

yukicoder

結果

テストケース

ソースコード