結果

問題 No.674 n連勤
コンテスト
ユーザー ats5515
提出日時 2018-04-13 23:08:54
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 198 ms / 2,000 ms
コード長 2,228 bytes
コンパイル時間 1,005 ms
コンパイル使用メモリ 100,448 KB
実行使用メモリ 21,552 KB
最終ジャッジ日時 2024-06-26 21:54:01
合計ジャッジ時間 2,890 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD = 1000000007;
struct UnionFind {
	vector<int> data;
	vector<int> mn;
	UnionFind(int size) {
		data.resize(size, -1);
		mn.resize(size, -1);
		for (int i = 0; i < size; i++) {
			mn[i] = i;
		}
	}
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (x < y) swap(x, y);
			data[x] += data[y]; data[y] = x;
			mn[x] = min(mn[x], mn[y]);
		}
		return x != y;
	}
	bool findSet(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};
template <class T>
struct fenwick_tree {
	vector<T> x;
	fenwick_tree(int n) : x(n, 0) { }
	T sum(int i, int j) {
		if (i == 0) {
			T S = 0;
			for (j; j >= 0; j = (j & (j + 1)) - 1) S += x[j];
			return S;
		}
		else return sum(0, j) - sum(0, i - 1);
	}
	void add(int k, T a) {
		for (; k < x.size(); k |= k + 1) x[k] += a;
	}
};
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int D, Q;
	cin >> D >> Q;
	vector<int> A(Q);
	vector<int> B(Q);
	map<int, int> mp;
	vector<int> inv;
	for (int i = 0; i < Q; i++) {
		cin >> A[i] >> B[i];
		mp[A[i]] = 0;
		mp[A[i] + 1] = 0;
		mp[A[i] - 1] = 0;
		mp[B[i]] = 0;
		mp[B[i] + 1] = 0;
		mp[B[i] - 1] = 0;
	}
	for (auto m : mp) {
		inv.push_back(m.first);
	}
	for (int i = 0; i < inv.size(); i++) {
		mp[inv[i]] = i;
	}
	fenwick_tree<int> ft((int)inv.size() + 1);
	UnionFind uf((int)inv.size());
	int res = 1;
	for (int i = 0; i < Q; i++) {
		A[i] = mp[A[i]];
		B[i] = mp[B[i]];
		ft.add(A[i], 1);
		ft.add(B[i] + 1, -1);
		if (A[i] > 0) {
			if (ft.sum(0, A[i] - 1) > 0) {
				uf.unionSet(A[i] - 1, A[i]);
			}
		}
		int x = A[i];
		//cerr << "st = " << A[i] << endl;
		while (true) {
			if (x + 1 < (int)inv.size() && ft.sum(0, x + 1) > 0) {
				uf.unionSet(x, x + 1);
			}
			else {
				break;
			}
			x = uf.root(x);
			//cerr << "x=" << x << endl;
		}
		res = max(res, inv[x] - inv[uf.mn[x]] + 1);
		//cerr << x << " " << uf.mn[x] << endl;
		cout << res << endl;
	}

}
0