結果

問題 No.686 Uncertain LIS
コンテスト
ユーザー kriii
提出日時 2018-12-08 22:54:45
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 530 bytes
コンパイル時間 554 ms
コンパイル使用メモリ 57,552 KB
実行使用メモリ 10,624 KB
最終ジャッジ日時 2024-09-14 14:19:42
合計ジャッジ時間 4,580 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 WA * 4 TLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <bitset>
using namespace std;

const int lim = 100000;
bitset<lim+1> now;

int f(int y)
{
	int l = y-1, r = lim+1;
	while (l + 1 < r){
		int m = (l + r) / 2;
		if ((now >> m).count() >= 1) l = m;
		else r = m;
	}
	return l;
}

int main()
{
	int N; scanf ("%d",&N); while (N--){
		int x,y; scanf ("%d %d",&x,&y);
		int z = f(y);
		if (z >= y) now[z] = 0;

		auto v = ((now << (lim - y)) >> (lim - y + x)) << x;
		now ^= v;
		now ^= (v << 1);
		now[x] = 1;
	}

	printf ("%d\n",now.count());

	return 0;
}
0