QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#594266#6703. Tokens on the SegmentsGrunrayRE 0ms3672kbC++2014.4kb2024-09-27 20:47:142024-09-27 20:47:15

Judging History

你现在查看的是最新测评结果

  • [2024-09-27 20:47:15]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3672kb
  • [2024-09-27 20:47:14]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

//#define int long long

#define bit(x) (1LL << (x))
#define lowbit(x) (x & -x)
#define sq(x) ((x) * (x))

#define rep(a, b, c, d) for (int a = (b); a <= (c); a += (d))
#define fep(a, b, c, d) for (int a = (b); a >= (c); a -= (d))

using unll = unsigned long long;
using ll = long long;

/*--int128--*/
//inline __int128 read() {//__int128模板 
//	__int128 x = 0, f = 1;
//	char ch = getchar();
//	while (ch < '0' || ch > '9') { if (ch == '-')  f = -1; ch = getchar(); }
//	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
//	return x * f;
//}
//inline void print(__int128 x) {
//	if (x < 0) { putchar('-'); x = -x; }
//	if (x > 9)  print(x / 10);
//	putchar(x % 10 + '0');
//}
/*--fast read--*/
template<typename T> T read() {
	T X = 0; bool flag = true; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') flag = false; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { X = (X << 1) + (X << 3) + ch - '0'; ch = getchar(); }
	if (flag) return X;
	return ~(X - 1);
}
template<typename T> void write(T X) {
	if (X < 0) { putchar('-'); X = ~(X - 1); }
	int s[100], top = 0;
	while (X) { s[++top] = X % 10; X /= 10; }
	if (!top) s[++top] = 0;
	while (top) putchar(s[top--] + '0');
}
/*--const--*/
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3f;
const long long MODE = 998244353;

const int dx[] = { 1, 0,-1, 0,   1, 1,-1,-1 };
const int dy[] = { 0,-1, 0, 1,  -1, 1,-1, 1 };

const double eps = 1e-8;
double Pi = acos(-1.0);
/*--math--*/
long long qpow(long long x, long long y) {
	x %= MODE;
	long long res = 1;
	while (y) {
		if (y & 1) res = res * x % MODE;
		x = x * x % MODE;
		y >>= 1;
	}
	return res;
}
long long gcd(long long a, long long b) { // 最大公约数
	while (b ^= a ^= b ^= a %= b)
		;
	return a;
}
long long lcm(long long a, long long b) { // 最小公倍数
	return a / gcd(a, b) * b;
}

/*------------CODE------------*/

// int months[15] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };

//priority_queue<ll> pq;//这是一个大根堆q
//priority_queue<int, vector<int>, greater<int> >q;//这是一个小根堆q
//priority_queue<ll, vector<ll>, greater<ll> >pq; // 小根

const long long N = 1e6 + 50;
const long long M = 1e6 + 50;

ll n, m;

struct STRING
{
	// 哈希
	struct HASHE { // 下标从1开始
		const int Pri = 13331;
		unll p[N], h[N];
		unll val = 0;
		// 求一个串的哈希值相当于求前缀和
		unll init(string str) {
			p[0] = 1; h[0] = 0;
			int len = str.length();
			for (int i = 1; i < len; i++) {
				p[i] = p[i - 1] * Pri;
				h[i] = h[i - 1] * Pri + str[i];
			}
			val = h[len - 1];
			return val; // 当前串的哈希值
		}
		// 求子串的哈希值相当于求区间和
		unll getSubHash(int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; }
		bool isSameSub(int l1, int r1, int l2, int r2) { return getSubHash(l1, r1) == getSubHash(l2, r2); }
	};
	struct Binary_HASHE
	{
		unll lh[N], rh[N], p[N];
		const ll Pri = 131ll;
		char s[N], c[N];
		unll pos;
		//ll len;
		ll lhget(ll l, ll r) {
			return ((lh[r] - lh[l - 1] * p[r - l + 1] % MODE + MODE) % MODE + MODE) % MODE;
		}
		ll rhget(ll l, ll r) {
			return ((rh[l] - rh[r + 1] * p[r - l + 1] % MODE + MODE) % MODE + MODE) % MODE;
		}
		ll cal(ll x, ll d) {
			if (x >= d)
				return rhget(pos + x - d, pos + x - 1);
			else {
				ll res1 = rhget(pos, pos + x - 1);
				ll res2 = lhget(pos + x, pos + d - 1);
				return (res1 * p[d - x] % MODE + res2) % MODE;
			}
		}
		char Getchar(ll x, ll d) {
			if (x >= d) return s[pos + x - d];
			else return s[pos + d - 1];
		}
		bool check(ll x, ll y) {
			ll l = 0, r = n - pos;
			while (l < r) {
				ll mid = (l + r + 1) / 2;
				ll p = cal(x, mid);
				ll q = cal(y, mid);
				if (p == q)
					l = mid;
				else
					r = mid - 1;
			}
			l++;
			char _x = Getchar(x, l);
			char _y = Getchar(y, l);
			return  _x > _y;
		}
	};
	// 字典树
	struct Trie {
		int nex[N][65], cnt;
		int exist[N];  // 该结点结尾的[词]出现次数是多少
		bool done[N]; // 记录是否为一个[词]
		bool vis[N]; // 记录该[词]是否被访问
		void init() {
			for (int i = 0; i <= cnt; i++) for (int j = 0; j < 65; j++) nex[i][j] = 0;
			for (int i = 0; i <= cnt; i++) exist[i] = 0;
			cnt = 0;
		}
		int getAscii(char ch) { //  A-Z a-z 0-9
			int ascii = 0;
			if (isupper(ch))      ascii = int(ch - 'A');
			else if (islower(ch)) ascii = int(ch - 'a' + 26);
			else if (isdigit(ch)) ascii = int(ch - '0' + 52);
			return ascii;
		}
		void insert(string s) {  // 插入[词]
			int p = 0, len = s.length();
			for (int i = 0; i < len; i++) {
				int c = getAscii(s[i]);
				if (!nex[p][c]) nex[p][c] = ++cnt;  // 如果没有,就添加结点
				p = nex[p][c];
				++exist[p];
			}
			done[p] = 1; // 记录成为一个[词]
		}
		int find(string s) {  // 查找[词]
			int p = 0, len = s.length();
			for (int i = 0; i < len; i++) {
				int c = getAscii(s[i]);
				if (!nex[p][c]) return 0;
				p = nex[p][c];
			}
			if (done[p]) return exist[p]; // 有这个[词]
			return 0; // 没有这个[词]
		}
		int findUnique(string s) { // 查找[词],并且判断该[词]是否访问过
			int p = 0, len = s.length();
			for (int i = 0; i < len; i++) {
				int c = getAscii(s[i]);
				if (!nex[p][c]) return 0;
				p = nex[p][c];
			}
			if (done[p]) { // 有这个[词]
				if (vis[p]) return -1; // 重复访问
				vis[p] = true;
				return exist[p];
			}
			return 0;
		}
	};
	// 维护异或的字典树
	//给定一棵n点的带权树,结点下标1-n。寻找树中找两个结点,求最长的异或路径。
	//异或路径指的是指两个结点之间唯一路径上的所有边权的异或。
	struct xorTrie {
		vector<pair<int, long long> >adj[N];
		int cnt = 0, tot = 1, res = 0;
		int dis[N], ch[N << 5/*N * 32*/][2];

		void insert(int x) {
			for (int i = 30, u = 1; i >= 0; --i) {
				int c = ((x >> i) & 1);  // 二进制一位一位向下取
				if (!ch[u][c]) ch[u][c] = ++tot;
				u = ch[u][c];
			}
		}
		int get(int x) {
			int ans = 0;
			for (int i = 30, u = 1; i >= 0; --i) {
				int c = ((x >> i) & 1);
				if (ch[u][c ^ 1]) {  // 如果能向和当前位不同的子树走,就向那边走
					u = ch[u][c ^ 1];
					ans |= (1 << i);
				}
				else u = ch[u][c];
			}
			return res = max(res, ans);  // 更新答案
		}
		void add(int u, int v, int w) { adj[u].push_back({ v, w }); }
		void dfs(int u, int fa) {
			insert(dis[u]);
			get(dis[u]);
			for (auto it : adj[u]) {  // 遍历子节点
				int v = it.first;
				long long w = it.second;
				if (v == fa) continue;
				dis[v] = dis[u] ^ w;
				dfs(v, u);
			}
		}
	};

	// 前缀函数
		// 查找:字符串s, i from 0 to sub.size()-1 形成的子串 是否 有相等的真前缀和真后缀
		// 有的话,长度是pi[i]
	vector<int> prefix_function(string s) {
		int len = (int)s.length();
		vector<int> pi(len); // 前缀
		for (int i = 1; i < len; i++) {
			int j = pi[i - 1];
			while (j > 0 && s[i] != s[j]) j = pi[j - 1];
			if (s[i] == s[j]) j++;
			pi[i] = j;
		}
		return pi;
	}
	int getMinPeriod(string s) {
		vector<int>pi = prefix_function(s);

		int len = s.length();

		if (!(len % (len - pi[len - 1]))) return len - pi[len - 1];
		else return len;
	}
	// KMP
		// 在字符串中查找子串的位置
	vector<int> KMP(string text, string pattern) {
		string cur = pattern + '#' + text; // cur = sub + str
		int sz1 = text.size(), sz2 = pattern.size();
		vector<int> kmp;
		vector<int> pi = prefix_function(cur);
		for (int i = sz2 + 1; i <= sz1 + sz2; i++) {
			if (pi[i] == sz2) kmp.push_back(i - 2 * sz2);
		}
		return kmp;
	}
	// 统计每个前缀出现的次数
	vector<int> count_occurrences(vector<int> pi, int len) {
		vector<int> ans(len + 1);
		for (int i = 0; i < n; i++)
			ans[pi[i]]++;
		for (int i = n - 1; i > 0; i--)
			ans[pi[i - 1]] += ans[i];
		for (int i = 0; i <= n; i++)
			ans[i]++;
		return ans;
	}
	// 最小表示法
	ll minn_show(vector<ll> sec) {
		ll k = 0, i = 1, j = 2;
		// 破环成链
		rep(i, 0, n - 1, 1) sec[n + i] = sec[i];
		while (k < n && i < n && j < n) {
			for (k = 0; k < n && sec[(i + k) % n] == sec[(j + k) % n]; k++)
				;
			sec[(i + k) % n] > sec[(j + k) % n] ? i = i + k + 1 : j = j + k + 1;
			if (i == j) i++;
		}
		return min(i, j);
	}
	struct AC {
		int tr[N][26], tot;
		int e[N], fail[N];

		void insert(string s) {
			int u = 0;
			for (int i = 0; i < s.length(); i++) {
				if (!tr[u][s[i] - 'a']) tr[u][s[i] - 'a'] = ++tot;  // 如果没有则插入新节点
				u = tr[u][s[i] - 'a'];                              // 搜索下一个节点
			}
			e[u]++;  // 尾为节点 u 的串的个数
		}

		void build() {
			queue<int> q;
			for (int i = 0; i < 26; i++)
				if (tr[0][i]) q.push(tr[0][i]);
			while (q.size()) {
				int u = q.front();
				q.pop();
				for (int i = 0; i < 26; i++) {
					if (tr[u][i]) {
						fail[tr[u][i]] =
							tr[fail[u]][i];  // fail数组:同一字符可以匹配的其他位置
						q.push(tr[u][i]);
					}
					else tr[u][i] = tr[fail[u]][i];
				}
			}
		}
		int query(string s) {
			int u = 0, res = 0;
			for (int i = 0; i < s.length(); i++) {
				u = tr[u][s[i] - 'a'];  // 转移
				for (int j = u; j && e[j] != -1; j = fail[j])
					res += e[j], e[j] = -1;
			}
			return res;
		}
	};
	struct SAM {
		// 每次End 是代表新产生的位置的作用点
		// 新创建的数组要清空
		//const int Max = ((1e5 + 5) * 2); // M节点数量,字符串长度的两倍
		int ch[M][30], mxlen[M], par[M], tp[M];
		int End, tot;
		int siz[M];
		int newnod() {
			tot++;
			mxlen[tot] = par[tot] = 0;
			memset(ch[tot], 0, sizeof(ch[tot]));
			siz[tot] = 0;
			return tot;
		}
		void clear() { // 1 为 root
			tot = 0;
			End = newnod();
		}
		void extend(int c) {
			int p = End; End = newnod();
			mxlen[End] = mxlen[p] + 1;
			siz[End] = 1;
			for (; p && !ch[p][c]; p = par[p]) ch[p][c] = End;
			if (!p) par[End] = 1;
			else {
				int q = ch[p][c];
				if (mxlen[p] + 1 == mxlen[q]) par[End] = q;
				else {
					int nq = newnod(); mxlen[nq] = mxlen[p] + 1; // nq 是新产生的分叉点
					memcpy(ch[nq], ch[q], sizeof(ch[q]));
					par[nq] = par[q], par[End] = par[q] = nq;
					for (; ch[p][c] == q; p = par[p]) ch[p][c] = nq;
				}
			}
		}
		void build() {//倒叙循环满足拓扑
			static int cnt[M];
			rep(i, 0, tot, 1) cnt[i] = 0;
			rep(i, 1, tot, 1) cnt[mxlen[i]]++;
			rep(i, 1, tot, 1) cnt[i] += cnt[i - 1];
			fep(i, tot, 1, 1) tp[cnt[mxlen[i]]--] = i;
		}

	};
	// 回文树查询回文子串出现次数
	struct PAM {
		int sz, tot, last;
		int cnt[N], ch[N][26], len[N], fail[N];
		char s[N];

		int node(int l) {  // 建立一个新节点,长度为 l
			sz++;
			memset(ch[sz], 0, sizeof(ch[sz]));
			len[sz] = l;
			fail[sz] = cnt[sz] = 0;
			return sz;
		}
		void clear() {  // 初始化
			sz = -1;
			last = 0;
			s[tot = 0] = '$';
			node(0); node(-1);
			fail[0] = 1;
		}
		int getfail(int x) {  // 找后缀回文
			while (s[tot - len[x] - 1] != s[tot]) x = fail[x];
			return x;
		}
		void insert(char c, int i) {  // 建树
			s[++tot] = c;
			int now = getfail(last);
			if (!ch[now][c - 'a']) {
				int x = node(len[now] + 2);
				fail[x] = ch[getfail(fail[now])][c - 'a'];
				ch[now][c - 'a'] = x;
			}
			last = ch[now][c - 'a'];
			//if (i > n)// 若破链成环
			cnt[last]++;
		}
		long long solve() {
			long long ans = 0;
			for (int i = sz; i >= 0; i--) {
				cnt[fail[i]] += cnt[i];
			}
			for (int i = 2; i <= sz; i++) {  // 更新答案
				//if (len[i] > n) continue;// 若破链成环
				ans = (ans + (((1ll) * len[i] * cnt[i]) % MODE) * cnt[i]) % MODE;

			}
			return ans;
		}
	};
	//Lyndon 分解
	struct Lyndon
	{
		//s 的字典序严格小于 s 的所有后缀的字典序,我们称 s 是Lyndon 串。
		//例,a,b,ab,aab,abb,ababb,abcd 都是 Lyndon 串
		vector<int> duval_getRightPoint(string const& s) { // 下标从 1 开始
			int len = s.size(), i = 1;
			vector<string> lyndon;
			vector<int> right_point;
			while (i < len) {
				int j = i + 1, k = i;
				while (j < len && s[k] <= s[j]) {
					if (s[k] < s[j]) k = i;
					else k++;
					j++;
				}
				while (i <= k) {
					lyndon.push_back(s.substr(i, j - k)); // Lyndon串
					i += j - k;
					right_point.push_back(i);
				}
			}
			//return lyndon;
			return right_point;
		}
		//求这个字符串的所有前缀字符串中的最大字典序子串
		//子串的左端点就是数组 l[]
		//可以证明其右端点就是 子串最右端 即 i
		vector<int> duval_getMaxOrderSubstringLeftPoint(string const& s) {
			int len = s.size(), i = 1;
			vector<int>l(len + 5);
			while (i < len) {
				int j = i + 1, k = i;
				if (!l[i]) l[i] = i;
				//cout << i << ' ';
				while (j < len && s[k] >= s[j]) {
					if (!l[j]) l[j] = i;
					if (s[k] == s[j]) k++;
					else k = i;
					j++;
				}
				while (i <= k) i += j - k;
			}
			return l;
		}
		// 最小表示法
		string minCyclicString(string s) {
			s += s;
			int len = s.size();
			int i = 0, ans = 0;
			while (i < len / 2) {
				ans = i;
				int j = i + 1, k = i;
				while (j < len && s[k] <= s[j]) {
					if (s[k] < s[j]) k = i;
					else k++;
					j++;
				}
				while (i <= k) i += j - k;
			}
			return s.substr(ans, len / 2);
		}
	};

};

struct NODE
{
	int l, r;
	bool operator < (const NODE& node) const { return r > node.r; }
}c[N];

bool cmp(NODE a, NODE b) {
	if (a.l == b.l) return a.r < b.r;
	return a.l < a.r;
}

priority_queue<NODE>pq;


void solve() {

	cin >> n;
	rep(i, 1, n, 1) {
		cin >> c[i].l >> c[i].r;
	}

	sort(c + 1, c + 1 + n, cmp);

	while (!pq.empty()) pq.pop();

	int pos = c[1].l;
	int ans = 0, idx = 1;

	while (idx <= n) {
		while (idx <= n && c[idx].l <= pos && pos <= c[idx].r) pq.push(c[idx++]);
		while (!pq.empty() && pos < c[idx].l) {
			if (pos <= pq.top().r) pos++, ans++;
			pq.pop();
		}
		if (idx != n + 1) pos = c[idx].l;
	}

	while (!pq.empty()) {
		if (pos <= pq.top().r) ans++, pos++;
		pq.pop();
	}
	
	cout << ans << '\n';



}


signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	//freopen("wrt.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	signed T = 1;
	//scanf("%d", &T);
	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3672kb

input:

2
3
1 2
1 1
2 3
3
1 2
1 1
2 2

output:

3
2

result:

ok 2 number(s): "3 2"

Test #2:

score: -100
Runtime Error

input:

10000
6
5 19
7 12
10 10
4 14
1 12
5 11
7
3 5
1 10
12 15
2 13
8 11
5 20
11 14
18
6 17
6 9
6 20
2 7
1 11
16 19
2 5
1 14
5 8
14 19
4 7
11 19
11 13
2 9
3 12
12 13
19 19
13 16
11
11 13
1 2
14 17
15 16
12 17
15 17
6 7
8 11
12 19
3 8
10 19
18
6 9
16 18
13 15
14 15
9 13
2 8
12 18
8 16
16 18
3 18
1 12
4 13
1...

output:


result: