結果

問題 No.1508 Avoid being hit
ユーザー startcppstartcpp
提出日時 2021-05-15 00:26:25
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 219 ms / 3,000 ms
コード長 3,123 bytes
コンパイル時間 1,070 ms
コンパイル使用メモリ 88,824 KB
実行使用メモリ 10,180 KB
最終ジャッジ日時 2024-04-10 05:42:18
合計ジャッジ時間 6,846 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 186 ms
9,136 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 1 ms
6,944 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 2 ms
6,944 KB
testcase_12 AC 2 ms
6,940 KB
testcase_13 AC 2 ms
6,944 KB
testcase_14 AC 2 ms
6,940 KB
testcase_15 AC 2 ms
6,940 KB
testcase_16 AC 59 ms
6,944 KB
testcase_17 AC 33 ms
6,944 KB
testcase_18 AC 35 ms
6,944 KB
testcase_19 AC 48 ms
6,940 KB
testcase_20 AC 86 ms
9,672 KB
testcase_21 AC 55 ms
6,940 KB
testcase_22 AC 69 ms
7,368 KB
testcase_23 AC 79 ms
9,212 KB
testcase_24 AC 219 ms
10,180 KB
testcase_25 AC 203 ms
9,860 KB
testcase_26 AC 15 ms
6,940 KB
testcase_27 AC 102 ms
6,944 KB
testcase_28 AC 104 ms
6,940 KB
testcase_29 AC 209 ms
10,008 KB
testcase_30 AC 111 ms
6,940 KB
testcase_31 AC 182 ms
9,796 KB
testcase_32 AC 195 ms
9,972 KB
testcase_33 AC 55 ms
6,944 KB
testcase_34 AC 175 ms
8,940 KB
testcase_35 AC 18 ms
6,944 KB
testcase_36 AC 98 ms
6,944 KB
testcase_37 AC 45 ms
6,940 KB
testcase_38 AC 139 ms
7,172 KB
testcase_39 AC 90 ms
6,944 KB
testcase_40 AC 180 ms
8,960 KB
testcase_41 AC 104 ms
6,940 KB
testcase_42 AC 182 ms
9,100 KB
testcase_43 AC 214 ms
9,576 KB
testcase_44 AC 2 ms
6,940 KB
testcase_45 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

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 {
				if (prev == -1) prev = xs[j];	//prev == -1をつけ忘れてた…
			}
		}
		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