QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#594266 | #6703. Tokens on the Segments | Grunray | RE | 0ms | 3672kb | C++20 | 14.4kb | 2024-09-27 20:47:14 | 2024-09-27 20:47:15 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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...