关于省选T1
  • 板块学术版
  • 楼主TankYu
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/4/1 22:45
  • 上次更新2023/10/23 19:42:18
查看原帖
关于省选T1
408071
TankYu楼主2023/4/1 22:45

刚45min做的奇怪差分,能不能卡

#include <map>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define D double
#define LD long double
#define LL long long
#define ULL unsigned long long
#define S string
#define fi first
#define se second
#define mp make_pair
using namespace std;

int sum[400010];
int beg[400010], fin[400010];
vector<int> ans;

int main()
{
//	freopen("station4.in", "r", stdin);
//	freopen("station4.out", "w", stdout);
	int n, m, sta;
	cin >> n >> m >> sta;
	for (int i = 1; i <= m; i++)
	{
		int l, r;
		cin >> l >> r;
		l *= 2;
		r *= 2;
		sum[l]++;
		sum[r + 1]--;
		beg[l] = fin[r] = true;
	}
	for (int i = 1; i <= 2 * n; i++)
	{
		sum[i] += sum[i - 1];
	}
//	for (int i = 1; i <= 2 * n; i++)
//	{
//		if (i % 2 == 0)
//			cout << sum[i] << ' ';
//	}
//	cout << '\n';
//	for (int i = 1; i <= 2 * n; i++)
//	{
//		if (i % 2)
//		{
//			continue;
//		}
//		if (i == sta * 2)
//		{
//			cout << "* ";
//		}
//		else if (sum[i] == 0)
//		{
//			cout << "# ";
//		}
//		else if (sum[i] && (sum[i - 2] == 0 || sum[i + 2] == 0))
//		{
//			cout << "| ";
//		}
//		else
//		{
//			cout << "- ";
//		}
//	}
	for (int i = 2 * sta - 1; i >= 1; i--)
	{
		if (sum[i] == 0)
		{
			break;
		}
		if (beg[i])
		{
			ans.push_back(i / 2);
		}
	}
	for (int i = 2 * sta + 1; i <= 2 * n; i++)
	{
		if (sum[i] == 0)
		{
			break;
		}
		if (fin[i])
		{
			ans.push_back(i / 2);
		}
	}
	sort(ans.begin(), ans.end());
	for (auto i : ans)
	{
		cout << i << ' ';
	}
	return 0;
}

2023/4/1 22:45
加载中...