結果

問題 No.1508 Avoid being hit
コンテスト
ユーザー startcpp
提出日時 2021-05-15 00:21:15
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,070 bytes
コンパイル時間 1,433 ms
コンパイル使用メモリ 89,080 KB
実行使用メモリ 10,296 KB
最終ジャッジ日時 2024-10-02 07:12:18
合計ジャッジ時間 6,591 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 32 WA * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

//O(NQ)のdpを考えたときに、区間が4つ以上に分割されないと予想できたので、区間で持つ実装を+頑張ります+
//番兵すると端の場合分けが要らなくなって、区間のsplit, mergeはimos法すると楽.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;

struct Segment {
	int l, r;	//[l, r)
	Segment(int l, int r) { this->l = l; this->r = r; }
};

void print_segs(int id, vector<Segment> &segs) {
	cout << id << " : ";
	for (int i = 0; i < segs.size(); i++) {
		cout << "[" << segs[i].l << ", " << segs[i].r << ")";
		if (i + 1 < segs.size()) cout << ", ";
	}
	cout << endl;
}

int n, q;
vector<int> a, b;

signed main() {
	int i, j;
	
	cin >> n >> q;
	a.resize(q);
	b.resize(q);
	rep(i, q) cin >> a[i];
	rep(i, q) cin >> b[i];
	
	vector<vector<Segment>> segsList;
	
	vector<Segment> segs;
	segs.push_back(Segment(1, n + 1));
	//print_segs(0, segs);
	segsList.push_back(segs);
	
	rep(i, q) {
		vector<int> xs;
		xs.push_back(a[i]);
		xs.push_back(a[i] + 1);
		xs.push_back(b[i]);
		xs.push_back(b[i] + 1);
		xs.push_back(0);
		xs.push_back(1);
		xs.push_back(n + 1);
		xs.push_back(n + 2);
		rep(j, segs.size()) {
			xs.push_back(segs[j].l - 1);
			xs.push_back(segs[j].r + 1);
		}
		sort(xs.begin(), xs.end());
		xs.erase(unique(xs.begin(), xs.end()), xs.end());
		
		vector<int> imos(xs.size());
		rep(j, segs.size()) {
			int iter1 = lower_bound(xs.begin(), xs.end(), segs[j].l - 1) - xs.begin();
			int iter2 = lower_bound(xs.begin(), xs.end(), segs[j].r + 1) - xs.begin();
			imos[iter1]++;
			imos[iter2]--;
		}
		
		rep(j, (int)imos.size() - 1) imos[j + 1] += imos[j];
		
		int INF = 1e+8;
		imos[lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin()] -= INF;
		imos[lower_bound(xs.begin(), xs.end(), b[i]) - xs.begin()] -= INF;
		imos[lower_bound(xs.begin(), xs.end(), 0) - xs.begin()] -= INF;
		imos[lower_bound(xs.begin(), xs.end(), n + 1) - xs.begin()] -= INF;
		
		int prev = -1;
		vector<Segment> new_segs;
		for (j = 1; j < imos.size(); j++) {
			if (imos[j] <= 0) {
				if (prev != -1) {
					Segment seg = Segment(prev, xs[j]);
					new_segs.push_back(seg);
				}
				prev = -1;
			}
			else {
				prev = xs[j];
			}
		}
		segs = new_segs;
		//print_segs(i + 1, segs);
		if (segs.size() == 0) { cout << "NO" << endl; return 0; }
		segsList.push_back(segs);
	}
	
	cout << "YES" << endl;
	
	int pos = segsList[segsList.size() - 1][0].l;
	vector<int> reversed_ans;
	
	reversed_ans.push_back(pos);
	for (i = segsList.size() - 2; i >= 0; i--) {
		//cout << "i = " << i << ", pos = " << pos << endl;
		rep(j, segsList[i].size()) {
			int l = segsList[i][j].l;
			int r = segsList[i][j].r;
			int k;
			rep(k, 3) {
				int npos = pos - 1 + k;
				if (l <= npos && npos < r) {
					reversed_ans.push_back(npos);
					pos = npos;
					break;
				}
			}
			if (k < 3) break;
		}
		if (j == segsList[i].size()) assert(0);
	}
	
	for (i = reversed_ans.size() - 1; i >= 0; i--) {
		cout << reversed_ans[i] << endl;
	}
	return 0;
}
0