Znzryb's Blog

The 2025 ICPC 德国 German Collegiate Programming Contest——J. Jumbled Packets（使用22作为分隔符，其他地方不能出现22这样子的分隔符）

Posted on 2026-02-11 Edited on 2026-04-06

题目大意

这是一道交互题，你的程序会对每个测试用例被运行两次。

编码阶段（Encode）：给你一个长度为 $n$ 的二进制串 $s$ （仅含 0 和 1），你需要输出一个长度同为 $n$ 的三进制串（可使用 0、1、2）。

解码阶段（Decode）：你在编码阶段输出的三进制串会被做一次循环旋转（即取某个后缀拼上对应的前缀，也可能不旋转），然后作为输入给你。你需要根据这个被旋转过的三进制串，还原出编码阶段的原始二进制串。

换句话说，你需要设计一种编码方案，使得即使编码后的串被任意循环旋转，你仍然能唯一地解码出原始二进制串。编码串长度必须和原串相同，且只能使用三种字符。

数据范围： $1 \le n \le 10^5$ 。

样例 1：编码阶段，原始串为 001，编码输出 002。解码阶段，收到的是 002 循环旋转后的 200，需要还原出 001。

输入（编码阶段）：
Encode
3
001

输出：
002

输入（解码阶段）：
Decode
3
200

输出：
001

样例 2：编码阶段，原始串为 0100，编码输出 2100。解码阶段，收到的恰好没有旋转，仍为 2100，需要还原出 0100。

输入（编码阶段）：
Encode
4
0100

输出：
2100

输入（解码阶段）：
Decode
4
2100

输出：
0100

思路讲解

使用二二作为分隔符。其他地方不允许出现二二为分隔符的这个情况。

长度大于8位的时候，使用二二作为分隔符，把这个字符串，把二进制字符串的前8位转化为6位，然后前面添上二二。然后转换的这6位三进制字符串要求第一位不能为二，最后一位不能为二，然后其中不能有二二这样子的字符。然后这样子转好以后，然后就好了。这样子转好以后呢，在解码的时候，我们就能够看到这个22的地方，然后我们知道我们的22都是放在开头的，我们就知道这个字符串它到底被循环移动了几位。

之所以不用二作为分隔符，就是不用一个二作为分隔符，是因为只用一个二的话，那么相当于你后面的就是二进制的字符串了，你后面就是一个二进制的字符串了，它造成了非常大量的信息的损失，所以我们就选用二二作为分隔符。当然你也可以用三个二，用四个二作为分隔符，但是那个可能会更加复杂。谢谢，但是意思反正是这个意思。

那么如果说长度小于8位的时候呢？长度小于8位的时候，我们是这样子做，就是直接暴力的进行双射就可以了。

包括长度大于8位，怎么把那6位给转回8位，我们也是用双设，就是直接我们下面放一个这个代码吧，就是非常暴力的。

const ll len2=8,len3=6;
vector<string> two_s;
// 生成该长度的二进制串
for (ll status=0;status<(1<<len2);++status) {
    string sta;
    ll op_status=status;
    while (true) {
        if (op_status==0) {
            break;
        }
        sta.push_back('0'+(op_status&1));
        op_status/=2;
    }
    sta.resize(len2,'0');
    two_s.push_back(sta);
}
ll idx=0;
for (ll status=0;status<pow_three[len3];++status) {
    string sta;
    ll op_status=status;
    while (true) {
        if (op_status==0) {
            break;
        }
        sta.push_back('0'+op_status%3);
        op_status/=3;
    }
    sta.resize(len3,'0');
    // 不允许开头为 2 ,这个是因为如果说开头为二的话，会造成一些问题。就是开头二如果连着前面那个二，然后就就，它会造成一个连接，能相当于又造出来一个二二，这个是会造成混乱的。
    if (!(sta.find("22")==-1 && sta.front()!='2')) {
        continue;
    }
    three_to_two[sta]=two_s[idx];
    two_to_three[two_s[idx]]=sta;
    ++idx;
    if (idx>=two_s.size()) {
        break;
    }
}

AC代码

AC
https://qoj.ac/submission/2031795
AC
https://codeforces.com/gym/106129/submission/362719223

源代码

/**
 * Problem: J. Jumbled Packets
 * Contest: 2025
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106129/problem/J
 * Created: 2026-02-11 14:57:00
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define debug3d(a)                                         \
cerr << #a << " = [\n";                                \
for (int i = 0; i < (int)(a).size(); i++)              \
{                                                      \
cerr << "  [\n";                                   \
for (int j = 0; j < (int)(a[i]).size(); j++)       \
{                                                  \
cerr << "    [";                               \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k];     \
cerr << "]\n";                                 \
}                                                  \
cerr << "  ]\n";                                   \
}                                                      \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */
bool is_unique(const string &s,const map<string,string> &mp){
    for (int i=0;i<s.size();++i) {
        string ops=s;
        rotate(ops.begin(),ops.begin()+i+1,ops.end());
        if (mp.contains(ops)) {
            return false;
        }
    }
    return true;
}
string find_str(const string &s,const map<string,string> &mp) {
    for (int i=0;i<s.size();++i) {
        string ops=s;
        rotate(ops.begin(),ops.begin()+i+1,ops.end());
        auto it=mp.find(ops);
        if (it!=mp.end()) {
            return it->second;
        }
    }
    assert(true);
    return "Error";
}
void Solve() {
    string op;
    cin>>op;
    ll N;
    cin>>N;
    map<string,string> three_to_two;
    map<string,string> two_to_three;
    vector<ll> pow_three(20);
    pow_three[0]=1;
    for (int i=1;i<=15;++i) {
        pow_three[i]=pow_three[i-1]*3;
    }
    if (N<=8) {
        // len<=8 直接双射计算
        // 暴力生成这个长度 <=8 的双射
        do {
            for (ll len=1;len<=8;++len) {
                vector<string> two_s;
                // 生成该长度的二进制串
                for (ll status=0;status<(1<<len);++status) {
                    string sta;
                    ll op_status=status;
                    while (true) {
                        if (op_status==0) {
                            break;
                        }
                        sta.push_back('0'+(op_status&1));
                        op_status/=2;
                    }
                    sta.resize(len,'0');
                    two_s.push_back(sta);
                }
                ll idx=0;
                // 生成该长度的三进制串
                for (ll status=0;status<pow_three[len];++status) {
                    string sta;
                    ll op_status=status;
                    while (true) {
                        if (op_status==0) {
                            break;
                        }
                        sta.push_back('0'+op_status%3);
                        op_status/=3;
                    }
                    sta.resize(len,'0');
                    if (is_unique(sta,three_to_two)) {
                        three_to_two[sta]=two_s[idx];
                        two_to_three[two_s[idx]]=sta;
                        ++idx;
                    }
                    if (idx>=two_s.size()) {
                        break;
                    }
                }
            }
        }while (false);
    }else {
        const ll len2=8,len3=6;
        vector<string> two_s;
        // 生成该长度的二进制串
        for (ll status=0;status<(1<<len2);++status) {
            string sta;
            ll op_status=status;
            while (true) {
                if (op_status==0) {
                    break;
                }
                sta.push_back('0'+(op_status&1));
                op_status/=2;
            }
            sta.resize(len2,'0');
            two_s.push_back(sta);
        }
        ll idx=0;
        for (ll status=0;status<pow_three[len3];++status) {
            string sta;
            ll op_status=status;
            while (true) {
                if (op_status==0) {
                    break;
                }
                sta.push_back('0'+op_status%3);
                op_status/=3;
            }
            sta.resize(len3,'0');
            if (!(sta.find("22")==-1 && sta.front()!='2' && sta.back()!=2)) {
                continue;
            }
            three_to_two[sta]=two_s[idx];
            two_to_three[two_s[idx]]=sta;
            ++idx;
            if (idx>=two_s.size()) {
                break;
            }
        }
    }


    if (op=="Encode") {
        string s;
        cin >> s;
        if (N<=8) {
            cout<<two_to_three[s]<<"\n";
            return;
        }
        string pre8(s.begin(),s.begin()+8);
        string thr6=two_to_three[pre8];
        string code="22"+thr6+string(s.begin()+8,s.end());
        cout<<code<<"\n";
    }else {
        string s;
        cin >> s;
        if (N<=8) {
            cout<<find_str(s,three_to_two)<<"\n";
            return;
        }
        ll pos22=s.find("22");
        if (pos22==-1) {
            rotate(s.begin(),s.begin()+SZ(s)-1,s.end());
        }else {
            rotate(s.begin(),s.begin()+pos22,s.end());
        }
        string code=three_to_two[string(s.begin()+2,s.begin()+8)]+string(s.begin()+8,s.end());
        cout<<code<<"\n";
    }
    
    
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://qoj.ac/submission/2031795
AC
https://codeforces.com/gym/106129/submission/362719223

*/

心路历程（WA，TLE，MLE……）

The 2025 ICPC 德国 German Collegiate Programming Contest——A. Around the Table

Posted on 2026-02-11 Edited on 2026-04-06

题目大意

题目名称：Around the Table

题意总结：
公园里有一张乒乓球桌，初始时左边队列有 $\ell$ 个人，右边队列有 $r$ 个人。左边队首的人先持球。
游戏规则如下：

持球者将球打到对面，然后立刻跑到对面队列的队尾。
对面队首的人接球后成为新的持球者，重复上述过程。
假设游戏进行无限次（ $10^{10^{100}}$ 次击球），你需要计算总共会出现多少对不同的“对决组合”。
注意：两个人面对面即为一次对决，A 对战 B 与 B 对战 A 被视为同一种组合，不重复计算。

输入格式：
一行包含两个整数 $\ell$ 和 $r$ （ $2 \le \ell \le 10^9, 1 \le r \le 10^9$ ），分别表示初始时左侧和右侧的人数。

输出格式：
输出一个整数，表示会出现的不同对决组合的数量。

样例 1 解释：
输入：2 2
输出：6
假设左边初始为 A, B，右边初始为 D, E。
流程推演：

注意啊，题目实际上求的是面对面情况，就是面对面过的这个 pair 的数量。当然，这 Pair 是一个无序对。

A 对 D（记录组合 {A, D}）。A 击球后去右边队尾。局面变更为：左 [B]，右 [D, E, A]。
B 对 D（记录组合 {B, D}）。D 击球后去左边队尾。局面变更为：左 [B, D]，右 [E, A]。
B 对 E（记录组合 {B, E}）。B 击球后去右边队尾。局面变更为：左 [D]，右 [E, A, B]。
D 对 E（记录组合 {D, E}）。E 击球后去左边队尾。局面变更为：左 [D, E]，右 [A, B]。
D 对 A（组合 {A, D} 已存在）。D 击球后去右边队尾。局面变更为：左 [E]，右 [A, B, D]。
E 对 A（记录组合 {E, A}）。A 击球后去左边队尾。局面变更为：左 [E, A]，右 [B, D]。
E 对 B（组合 {B, E} 已存在）。E 击球后去右边队尾。局面变更为：左 [A]，右 [B, D, E]。
A 对 B（记录组合 {A, B}）。B 击球后去左边队尾。局面变更为：左 [A, B]，右 [D, E]。
此时回到初始局面（A 对 D），循环结束。
总共出现的不重复组合为：{A, D}, {B, D}, {B, E}, {D, E}, {E, A}, {A, B}，共 6 种。

思路讲解

AI 提示 1（遇到这种问题还是要打表，还是要打表。）

好的，你还没有开始写。这道题其实有很漂亮的结构，我来给你一些分层提示，你可以看一个想一下，不够再往下看。

提示 1（方向性）：手动模拟一下小例子（比如 ℓ=2, r=2），把所有玩家编号 0 到 n-1，观察每次击球后队列的变化。特别注意：每两次击球（左打一次、右打一次）之后，两边队列的长度会恢复到 ℓ 和 r。那么这两次击球之后，队首面对的人相比之前偏移了多少？

提示 2（核心观察）：给 n = ℓ + r 个人编号，排成一个环。初始时左队首是 0 号，右队首是 ℓ 号。你会发现：

第 2k 次击球时，面对的一对人是 $\{k \bmod n,\; (k + \ell) \bmod n\}$
第 2k+1 次击球时，面对的一对人是 $\{(k+1) \bmod n,\; (k + \ell) \bmod n\}$
也就是说，偶数次击球产生的配对，环上距离固定为 $\ell$ （等价于 $r$ ）；奇数次击球产生的配对，环上距离固定为 $\ell - 1$ （等价于 $r + 1$ ）。

提示 3（计数）：问题变成了：在 $\mathbb{Z}_n$ 的环上，

距离为 $d_1 = \min(\ell, r)$ 的无序对有多少个？
距离为 $d_2 = \min(\ell - 1, r + 1)$ 的无序对有多少个？
这两个集合是否可能重合？
对于一个固定距离 $d$ （ $1 \le d \le n/2$ ）， $n$ 个人的环上距离恰好为 $d$ 的无序对有多少个？想想什么时候是 $n$ ，什么时候是 $n/2$ 。
然后考虑 $d_1$ 和 $d_2$ 什么时候相等（此时两类配对产生的是同一个集合，不能重复计数）。

这三层提示应该足够你推出最终公式了。要继续深入还是先自己想一下？

_______________[ Sample Testcase #1 INPUT ]_______________
2 2

_______________[ Sample Testcase #1 OUTPUT]_______________
6


[-] FAILURE: RUNTIME ERROR
2 3
1 3
1 4
3 4
3 2
4 2
4 1
2 1
2 3
1 3
1 4

我们还是把第一个数字给反转一下吧，把第一个数字反转一下更加符更加符合我们人类的这个直觉。

你会发现一二三四五，这样子是轮流出现的，是轮流出现的，就像模运算一样。

_______________[ Sample Testcase #1 INPUT ]_______________
2 2

_______________[ Sample Testcase #1 OUTPUT]_______________
6


[-] FAILURE: RUNTIME ERROR
1 3
2 3
2 4
3 4
3 1
4 1
4 2
1 2
1 3
2 3
2 4

_______________[ Sample Testcase #2 INPUT ]_______________
2 3

_______________[ Sample Testcase #2 OUTPUT]_______________
10


[-] FAILURE: RUNTIME ERROR
1 3
2 3
2 4
3 4
3 5
4 5
4 1
5 1
5 2
1 2
1 3
2 3
2 4
3 4
3 5
4 5
4 1
5 1
5 2
1 2
1 3

规律大概是这样的，不过还是不是特别清楚呢。我们使用零 base 的下标再注释一下。

这下子这个规律就非常清楚了。不过注意啊，其实就是第奇数个加 gap ，第偶数个加 gap-1，它不会加 gap 加二什么之类的。

那么奇数位， $(i,(i+gap)\mod n)$ ，这个东西内部，有没有可能重复呢？不难写出：

i\equiv i'+gap \\ i+gap\equiv i' \\

art

i      ≡ i' + gap  (mod n)    ①
i + gap ≡ i'        (mod n)    ②

① - ②:  -gap ≡ gap  (mod n)
即:      2 * gap ≡ 0  (mod n)

注意啊，处理这种同余式子可以加减乘，但是不能除。如果除的话，必须确保逆元存在。逆元存在条件就是你要除的数字和和这个 mod n 的这个 n 是互质的。

注意啊，处理各种各样的式子，这个都是先要把这个变量给消掉，对吧？这个 i 和 i’ 都是变量，它们这个式子非常优美，可以直接消掉。

我们接下来看，就是说i 加 gap 和 i 加 gap 减一这两个环是否会有相同的情况。

如上图所示，无非其实就是两种相同的情况嘛。

那么另外一种情况就是有可能成立的了。也就是二 gap 减一，和百分之 n，mod n 是零。

void Solve() {
    ll L,R;
    cin >> L >> R;
    ll N=L+R;
    // 就是 L
    ll gap1=(L+1)-1;
    ll ans1=N;
    // 如果是这个重复了，由于与这个 i 无关，因此所有 i 都有相同，总个数就是 N/2
    if (2*gap1%N==0) {
        ans1=N/2;
    }
    ll gap2=gap1-1;
    ll ans2=N;
    if (2*gap2%N==0) {
        ans2=N/2;
    }
    // 相同情况处理
    if ((gap1+gap2)%N==0) {
        ans2=0;
    }
    cout<<ans1+ans2<<"\n";
}

AC代码

AC
https://qoj.ac/submission/2027025

源代码

/**
 * Problem: Around the Table
 * Contest: QOJ
 * Judge: Virtual Judge
 * URL: https://vjudge.net/problem/QOJ-14560
 * Created: 2026-02-11 12:20:26
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define debug3d(a)                                         \
cerr << #a << " = [\n";                                \
for (int i = 0; i < (int)(a).size(); i++)              \
{                                                      \
cerr << "  [\n";                                   \
for (int j = 0; j < (int)(a[i]).size(); j++)       \
{                                                  \
cerr << "    [";                               \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k];     \
cerr << "]\n";                                 \
}                                                  \
cerr << "  ]\n";                                   \
}                                                      \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */

void Solve() {
    ll L,R;
    cin >> L >> R;
    ll N=L+R;
    // 就是 L
    ll gap1=(L+1)-1;
    ll ans1=N;
    if (2*gap1%N==0) {
        ans1=N/2;
    }
    ll gap2=gap1-1;
    ll ans2=N;
    if (2*gap2%N==0) {
        ans2=N/2;
    }
    if ((gap1+gap2)%N==0) {
        ans2=0;
    }
    cout<<ans1+ans2<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://qoj.ac/submission/2027025

*/

心路历程（WA，TLE，MLE……）

The 2025 ICPC 德国 German Collegiate Programming Contest——K. Karlsruhe Skyline

Posted on 2026-02-11 Edited on 2026-04-06

题目大意

题目描述
你需要构造一个包含整数 $1$ 到 $n$ 的排列（即长度为 $n$ 的序列，其中 $1 \sim n$ 每个数字出现且仅出现一次）。
在这个序列中，我们将数字视为楼房的高度。定义“可见性”规则如下：

从某一侧观察，如果一个数字严格大于它和观察点之间的所有数字，则该数字是可见的（即较高的楼会挡住后面较矮的楼）。

请构造一个排列，同时满足以下两个条件：

从左向右看，恰好有 $a$ 个数字是可见的。
从右向左看，恰好有 $b$ 个数字是可见的。

输入格式
输入包含一行三个整数 $n, a, b$ 。
数据范围： $2 \le n \le 1000$ ， $1 \le a, b \le n$ 。

输出格式

如果存在满足条件的排列，首先输出一行 yes，随后输出 $n$ 个整数，表示构造出的排列。如果有多个解，输出任意一个即可。
如果不存在满足条件的排列，输出 no。

样例解释

样例 1
输入：5 2 2
输出：yes 1 5 2 3 4
解释：

左侧视角：看到 1，接着看到 5（5 > 1）。后面的 2, 3, 4 都比 5 小，被 5 挡住。共看见 2 个，满足 $a=2$ 。
右侧视角：看到 4，3 和 2 被 4 挡住。接着看到 5（5 > 4）。1 被 5 挡住。共看见 2 个（4 和 5），满足 $b=2$ 。

样例 2
输入：5 3 4
输出：no
解释：在 $n=5$ 的情况下，无法构造出左看 3 个、右看 4 个的排列。

样例 4
输入：4 1 4
输出：yes 4 3 2 1
解释：

左侧视角：第一个是 4（最大值），挡住了后面所有的数。共看见 1 个，满足 $a=1$ 。
右侧视角：从右往左依次是 1, 2, 3, 4，每一个都比右边的前序数字大。共看见 4 个，满足 $b=4$ 。

思路讲解

这个这道题目还是很简单的。这个无解的情况已经高亮出来了。A 等于等于一，B 等于等于一，肯定是不可能的。因为你一定能够看到一个次高的和一个最高的。所以说你你是不可能你是不可能就是只看到一个建筑的。那么 A 加 B 大于 N 加一的话也是不可能的。因为两边看，从一边看过去，再从另外一边看过去的总和加在一起，不可能超过 N 加一。因为一定有一个最高的建筑会把你给挡住的。所以两边的总和其实就是两边，这边就是，两边它加起来最大就是 N 加一。

后面构造也是比较简单，反正就是要注意这个顺序的，就是要注意一下顺序，就是要注意一下顺序。然后还有最高的建筑一定能被看到这个限制。就是记住这个，然后你用一个 DQ 去构造会简单一点。

void Solve() {
    ll N,a,b;
    cin >> N >> a >> b;
    //  无解的情况
    if (a==1 && b==1) {
        cout<<"no\n";
        return;
    }
    if (a+b>N+1) {
        cout<<"no\n";
        return;
    }
    vector<ll> ans_ls(N+2);
    deque<ll> q;
    for (int i=1;i<=N-2;++i) {
        q.push_back(i);
    }
    if (a==1) {
        ans_ls[1]=N;
        for (ll i=N;i>=2;--i) {
            if (i==N-b+2) {
                ans_ls[i]=N-1;
            }else {
                ans_ls[i]=q.front();
                q.pop_front();
            }
        }
    }else if (b==1){
        // ll cnt=0;
        ans_ls[N]=N;
        for (int i=1;i<=N-1;++i) {
            if (i==a-1) {
                ans_ls[i]=N-1;
            }else {
                // ++cnt;
                ans_ls[i]=q.front();
                q.pop_front();
            }
        }
    }else {
        ll cnt=0;
        for (int i=1;i<=N;++i) {
            if (i==a-1) {
                ans_ls[i]=N-1;
            }else if (i==N-b+1) {
                ans_ls[i]=N;
            }else if (i<a-1){
                ans_ls[i]=q.front();
                q.pop_front();
            }else {
                ans_ls[i]=q.back();
                q.pop_back();
            }
        }
    }
    cout<<"yes\n";
    for (int i=1;i<=N;++i) {
        cout<<ans_ls[i]<<" ";
    }
    cout<<"\n";
}

AC代码

AC
https://qoj.ac/submission/2026555

源代码

/**
 * Problem: Karlsruhe Skyline
 * Contest: QOJ
 * Judge: Virtual Judge
 * URL: https://vjudge.net/problem/QOJ-14570
 * Created: 2026-02-11 13:14:57
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define debug3d(a)                                         \
cerr << #a << " = [\n";                                \
for (int i = 0; i < (int)(a).size(); i++)              \
{                                                      \
cerr << "  [\n";                                   \
for (int j = 0; j < (int)(a[i]).size(); j++)       \
{                                                  \
cerr << "    [";                               \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k];     \
cerr << "]\n";                                 \
}                                                  \
cerr << "  ]\n";                                   \
}                                                      \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */

void Solve() {
    ll N,a,b;
    cin >> N >> a >> b;
    if (a==1 && b==1) {
        cout<<"no\n";
        return;
    }
    if (a+b>N+1) {
        cout<<"no\n";
        return;
    }
    vector<ll> ans_ls(N+2);
    deque<ll> q;
    for (int i=1;i<=N-2;++i) {
        q.push_back(i);
    }
    if (a==1) {
        ans_ls[1]=N;
        for (ll i=N;i>=2;--i) {
            if (i==N-b+2) {
                ans_ls[i]=N-1;
            }else {
                ans_ls[i]=q.front();
                q.pop_front();
            }
        }
    }else if (b==1){
        // ll cnt=0;
        ans_ls[N]=N;
        for (int i=1;i<=N-1;++i) {
            if (i==a-1) {
                ans_ls[i]=N-1;
            }else {
                // ++cnt;
                ans_ls[i]=q.front();
                q.pop_front();
            }
        }
    }else {
        ll cnt=0;
        for (int i=1;i<=N;++i) {
            if (i==a-1) {
                ans_ls[i]=N-1;
            }else if (i==N-b+1) {
                ans_ls[i]=N;
            }else if (i<a-1){
                ans_ls[i]=q.front();
                q.pop_front();
            }else {
                ans_ls[i]=q.back();
                q.pop_back();
            }
        }
    }
    cout<<"yes\n";
    for (int i=1;i<=N;++i) {
        cout<<ans_ls[i]<<" ";
    }
    cout<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://qoj.ac/submission/2026555

WA
https://qoj.ac/submission/2026545

*/

心路历程（WA，TLE，MLE……）

The 2025 ICPC 德国 German Collegiate Programming Contest——L. Labour Laws

Posted on 2026-02-11 Edited on 2026-04-06

题目大意

题目描述

根据德国《工作时间法》（ArbZG），员工的工作与休息时间需遵守以下规定：

如果单日实际工作时间超过 6 小时，必须至少休息 30 分钟。
如果单日实际工作时间超过 9 小时，必须至少休息 45 分钟。
单日工作时间严禁超过 10 小时。

定义“在岗总时间”为：

在岗总时间 = 实际工作时间 + 休息时间

给定一名员工当天的在岗总时间 $t$ （分钟），因为忘记了具体的打卡记录，为了确保不违反法律，请计算该员工为了使工作时间合法，其中最少必须包含多少分钟的休息时间。

输入格式

包含一行一个整数 $t$ ( $0 \le t \le 1440$ )，表示当天的在岗总时间（分钟）。

输出格式

输出一个非负整数，表示使该工作时长合法的最小休息时间（分钟）。

样例解释

样例 1
输入：495
输出：30
解释：总时间 495 分钟。如果休息 30 分钟，实际工作时间为 $495 - 30 = 465$ 分钟（7 小时 45 分）。因为 $465 > 360$ （6 小时），法律要求至少休息 30 分钟。当前休息时间 30 分钟满足要求。
样例 2
输入：360
输出：0
解释：总时间 360 分钟。如果休息 0 分钟，实际工作时间为 360 分钟（6 小时）。未超过 6 小时，法律不强制要求休息。
样例 3
输入：540
输出：30
解释：总时间 540 分钟。如果休息 0 分钟，实际工作 $540 > 360$ ，违规。如果休息 30 分钟，实际工作 $510$ 分钟（8.5 小时），超过 6 小时但不超过 9 小时，需休息 30 分钟，满足要求。
样例 4
输入：0
输出：0
解释：没上班，不需要休息。

思路讲解

之所以这道题目它有点阴啊，就是因为它计算的是这个实际工作时间，然后它会有一些空隙。

我们这个 min max 指的是什么呢？就是要么把工作时间降到360分钟以下，接受0小时休息，要么把工作时间降到540分钟以下接受30分钟休息，要么把工作时间降到600分钟以下，结束45分钟休息。

void Solve() {
    ll N;
    cin >> N;
    cout << min({max(0ll, N - 360), max(30ll, N - 540), max(45ll, N - 600)}) << "\n";
}

AC代码

AC
https://qoj.ac/submission/2026351

源代码

/**
 * Problem: Labour Laws
 * Contest: QOJ
 * Judge: Virtual Judge
 * URL: https://vjudge.net/problem/QOJ-14571
 * Created: 2026-02-11 12:25:54
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define debug3d(a)                                         \
cerr << #a << " = [\n";                                \
for (int i = 0; i < (int)(a).size(); i++)              \
{                                                      \
cerr << "  [\n";                                   \
for (int j = 0; j < (int)(a[i]).size(); j++)       \
{                                                  \
cerr << "    [";                               \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k];     \
cerr << "]\n";                                 \
}                                                  \
cerr << "  ]\n";                                   \
}                                                      \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */

void Solve() {
    ll N;
    cin >> N;
    cout << min({max(0ll, N - 360), max(30ll, N - 540), max(45ll, N - 600)}) << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://qoj.ac/submission/2026351

*/

心路历程（WA，TLE，MLE……）

2025_ICPC_NERC_Northern_Eurasia_Finals——D. Doorway（扫描线的本质就是遍历一个出一个）（扫描线特别适合处理区间重合相关问题）

Posted on 2026-02-09 Edited on 2026-04-06

题目大意

题目总结：D. Doorway

说白了就是告诉你滑动门两边的墙壁，告诉你从左到右的滑动门的这个长度。然后有好几层的这样子的子的滑动门系统问你这样子的系统能够张开的最大口子长度是多少。

问题描述

在一个多层滑动门系统中，共有 $n$ 层。每一层可以看作一个水平区间，由左侧墙壁 $x_{i,1}$ 和右侧墙壁 $x_{i,2}$ 限定。每一层包含若干扇固定长度的滑动门，门可以在该层的墙壁范围内自由左右滑动，但不能相互重叠，也不能越过墙壁。

目标

寻找一个最大的开口（Opening）。开口定义为一个水平区间，使得在所有层中，该区间内的任何位置都没有任何门或墙壁遮挡。你需要通过调整每一层门的位置，使得这个公共开口的长度最大化。

输入格式

第一行：层数 $n$ ( $1 \le n \le 10^5$ )。
接下来的 $n$ 行，每行描述一层：
- 三个整数：门数量 $k_i$ 、左墙坐标 $x_{i,1}$ 、右墙坐标 $x_{i,2}$ ( $0 \le x_{i,1} < x_{i,2} \le 10^9$ )。
- $k_i$ 个整数：该层从左到右每扇门的长度 $l_{i,j}$ 。
数据保证 $\sum k_i \le 3 \cdot 10^5$ 。

输出格式

一个整数，表示通过移动门所能达到的最大公共开口长度。

样例解释

样例 1

输入：
- 第 1 层：墙在 $[2, 11]$ ，门长 3 和 2。
- 第 2 层：墙在 $[4, 12]$ ，门长 1, 1 和 2。
逻辑：
所有层的共同墙壁限制区间为 $[\max(x_{i,1}), \min(x_{i,2})]$ ，即 $[4, 11]$ ，长度为 7。
- 在第 1 层中，如果将长为 3 的门推到最左，长为 2 的门推到最右，中间会留出空隙。
- 在第 2 层中，通过合理分配门的位置，可以使得在 $[4, 11]$ 这个范围内，所有层共同暴露出的最大空白区间长度为 4。

样例 2

输入：
- 第 1 层：墙在 $[0, 7]$ ，门长 2 和 4（总长 6，空隙 1）。
- 第 2 层：墙在 $[4, 9]$ ，门长 4（总长 4，空隙 1）。
逻辑：
第一层有效范围 $[0, 7]$ ，第二层有效范围 $[4, 9]$ ，它们的交集是 $[4, 7]$ ，长度仅为 3。由于两层中都存在长度大于或等于交集长度的门或门组限制，无法在所有层中腾出一个完全没有遮挡的公共区间。
输出： 0

注意

这个示例展示了第一个例子的解决方案。墙壁填充黑色，门填充各种灰色，开口是白色。当每层的第一个门向左移动，其余的门向右移动时，我们得到了最大的开口为4。

思路讲解

还是一样的思路啊，就是当你发现你只知道起始位置的时候，你会发现计算这个东西啊，其实不是很容易。

当然，我们上面所指的起始位置，其实是指的总体的起始位置。考虑到，虽然说总体的起始位置，知道总体的起始位置，然后我们去进行一个这个操作，它其实也是需要 $O(N)$ 吧。

那我们曾经提及过非常多次，当我们发现采用总体的想法碰壁的时候，我们应该怎么样？我们应该采用更加细颗粒度的东西，是不是？因此我们可以采用每一个起始位置，就是每一个滑窗系统的起始位置，去解决以及考虑这个问题。

AI 的模拟

这道题维护的是：每层的"gap 右端点"，一共 $N$ 个值。
具体来说，multiset 里始终有 $N$ 个数，第 $i$ 层占一个位置，表示"在当前扫描位置下，第 $i$ 层的空隙最远能延伸到哪里"。
我画一下扫描过程，用样例来说明。

样例模拟

1
2
3

2
2 2 11 3 2
3 4 12 1 1 2

层 1： $x_1=2$ ， $x_2=11$ ，门 $=[3,2]$ ， $w=4$ 。gap-start 候选： $2, 5, 7$ ，对应 rightend： $6, 9, 11$ 。
层 2： $x_1=4$ ， $x_2=12$ ，门 $=[1,1,2]$ ， $w=4$ 。gap-start 候选： $4, 5, 6, 8$ ，对应 rightend： $8, 9, 10, 12$ 。
所有事件排序：

扫到 $g$	属于哪层	新 rightend	multiset 状态	$\min - g$
$2$	层1	$6$	$\{6, -\infty\}$	层2还没激活
$4$	层2	$8$	$\{6, 8\}$	$6-4=2$
$5$	层1	$9$	$\{9, 8\}$	$8-5=3$
$5$	层2	$9$	$\{9, 9\}$	$9-5=\mathbf{4}$
$6$	层2	$10$	$\{9, 10\}$	$9-6=3$
$7$	层1	$11$	$\{11, 10\}$	$10-7=3$
$8$	层2	$12$	$\{11, 12\}$	$11-8=3$
答案 = $4$ ，在 $g=5$ 时取到。
multiset 里的含义：在扫描位置 $g=5$ 时，层 1 的空隙最远能到 $9$ ，层 2 的空隙最远能到 $9$ 。取最小值 $9$ ，opening = $9 - 5 = 4$ 。
所以维护的东西就是这 $N$ 个"每层能延伸到多远"的值，用 multiset 随时拿最小值。

2025 United Kingdom and Ireland Programming Contest (UKIEPC 2025) 2025 英国 ICPC——B. Brickwork（判断砖块是否重叠）（扫描线的本质就是遍历一个出一个）（维护一个当前生效的集合）
为什么这道题目你需要去塞一个负无穷呢？是这样子的，这个是因为啊，我们另外一道题目就是这个 brick work 是处理这个不相交问题，但这道题目我们处理的是相交问题。不相交问题你自然是还没有启用的区间，你自然是不用往里面去塞的。但是集合相交问题，还没有启用的集合，需要往里塞一个未启用值，就是未生效值。因为它都没启用，它肯定是不相交的对吧，为了避免这种情况影响我们的最终判断，我们需要往里面塞一个未启用值？

multiset<ll> ri_st;
// vector<Event> event_ls;
vector<ll> i_ri_ls(N + 2);
map<ll, vector<Event> > x1_idx_x2_mtx;
for (int i = 1; i <= N; ++i) {
    ll sum = accumulate(all(door_mtx[i]), 0ll);
    auto [x1,x2] = wall_pos[i];
    x2 -= sum;
    // 在没有碰到自己的左端点之前，这个滑动系统不应该贡献任何的这个有效的右端点。
    ri_st.insert(-INF);
    i_ri_ls[i] = -INF;
    x1_idx_x2_mtx[x1].push_back({i, x2});
    for (auto v: door_mtx[i]) {
        x1 += v;
        x2 += v;
        x1_idx_x2_mtx[x1].push_back({i, x2});
    }
}
ll ans = 0;
for (auto &[x1,vec]: x1_idx_x2_mtx) {
    for (auto &[id,x2]: vec) {
        ri_st.erase(ri_st.find(i_ri_ls[id]));
        ri_st.insert(x2);
        i_ri_ls[id] = x2;
    }
    ans = max(ans, *ri_st.begin() - x1);
}

AC代码

AC
https://codeforces.com/contest/2181/submission/362349671

源代码

/**
 * Problem: D. Doorway
 * Contest: 2025
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2181/problem/D
 * Created: 2026-02-11 00:56:58
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#include <iostream>

#define debug1d(a) do { \
std::cerr << #a << " = ["; \
bool first = true; \
for (const auto &x : a) { \
if (!first) std::cerr << ", "; \
std::cerr << x; \
first = false; \
} \
std::cerr << "]\n"; \
} while (0)

#define debug2d(a) do { \
std::cerr << #a << " = [\n"; \
for (const auto &row : a) { \
std::cerr << "  ["; \
bool first = true; \
for (const auto &x : row) { \
if (!first) std::cerr << ", "; \
std::cerr << x; \
first = false; \
} \
std::cerr << "]\n"; \
} \
std::cerr << "]\n"; \
} while (0)

#define debug3d(a) do { \
std::cerr << #a << " = [\n"; \
for (const auto &mat : a) { \
std::cerr << "  [\n"; \
for (const auto &row : mat) { \
std::cerr << "    ["; \
bool first = true; \
for (const auto &x : row) { \
if (!first) std::cerr << ", "; \
std::cerr << x; \
first = false; \
} \
std::cerr << "]\n"; \
} \
std::cerr << "  ]\n"; \
} \
std::cerr << "]\n"; \
} while (0)
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT, testcase;

/*
 *
 */
struct Wall_pos {
    ll x1, x2;
};

struct Event {
    ll idx/*,x1*/, x2;
    // bool operator<(const Event &o) const {
    //     if (x1!=o.x1) return x1<o.x1;
    //     return idx<o.idx;
    // }
};

void Solve() {
    ll N;
    cin >> N;
    vector<vector<ll> > door_mtx(N + 2);
    vector<Wall_pos> wall_pos(N + 2);
    ll mxx1 = 0, mnx2 = INF;
    for (int i = 1; i <= N; ++i) {
        ll K, x1, x2;
        cin >> K >> x1 >> x2;
        wall_pos[i] = {x1, x2};
        mxx1 = max(mxx1, x1);
        mnx2 = min(mnx2, x2);
        door_mtx[i].resize(K);
        for (auto &v: door_mtx[i]) {
            cin >> v;
        }
    }
    multiset<ll> ri_st;
    // vector<Event> event_ls;
    vector<ll> i_ri_ls(N + 2);
    map<ll, vector<Event> > x1_idx_x2_mtx;
    for (int i = 1; i <= N; ++i) {
        ll sum = accumulate(all(door_mtx[i]), 0ll);
        auto [x1,x2] = wall_pos[i];
        x2 -= sum;
        // 在没有碰到自己的左端点之前，这个滑动系统不应该贡献任何的这个有效的右端点。
        ri_st.insert(-INF);
        i_ri_ls[i] = -INF;
        x1_idx_x2_mtx[x1].push_back({i, x2});
        for (auto v: door_mtx[i]) {
            x1 += v;
            x2 += v;
            x1_idx_x2_mtx[x1].push_back({i, x2});
        }
    }
    ll ans = 0;
    for (auto &[x1,vec]: x1_idx_x2_mtx) {
        for (auto &[id,x2]: vec) {
            ri_st.erase(ri_st.find(i_ri_ls[id]));
            ri_st.insert(x2);
            i_ri_ls[id] = x2;
        }
        ans = max(ans, *ri_st.begin() - x1);
    }
// #ifdef LOCAL
//     debug2d(x1_idx_x2_mtx);
// #endif
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
    Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2181/submission/362349671

*/

心路历程（WA，TLE，MLE……）

AI 提示

好，我来认真讲一下这道 Doorway 的扫描线，以及和 Brickwork 的对比。

Doorway 扫描线的精妙之处

这道题的扫描线，最精妙的地方有三层递进：

第一层：观察到 gap 宽度是定值

每层的门总长是固定的，墙的区间也是固定的，所以每层的空隙宽度 $w_i = x_2 - x_1 - \sum l_j$ 是一个常数。不管你怎么滑动门，空隙的大小不变，变的只是空隙的位置。
这意味着原问题从"怎么安排门"变成了"从每层选一个空隙位置，使得所有层的空隙的交集最大"。

第二层：最优 st 必在 gap-start 处（这个说白了傻子都知道，所谓的gap start就是每层都有K种选择，纯纯是傻逼。）

opening 的左端点 st 如果确定了，那每层的最优策略就是：把空隙尽量往右推（把尽可能多的门放到 st 左边），这样右端点 $\text{rightend}_i(\text{st})$ 最大。
关键性质：在两个相邻的 gap-start 之间，所有层的 rightend 都不变，但 st 在递增，所以 $\min(\text{rightend}_i) - \text{st}$ 严格递减。
结论：最优 st 必然是某层的某个 gap-start 位置。候选点总共就 $\sum(k_i + 1)$ 个。

第三层：扫描线 + multiset 做到 O(sum_k * log n)

如果对每个候选 st 暴力算所有层的 rightend，复杂度是 $O(\sum k_i \times n)$ ，太慢。
精妙之处：把所有候选 st 排序后从左到右扫描，每次只有一层的 rightend 发生变化（就是当前 gap-start 所属的那一层）。用 multiset 维护所有层的 rightend， $O(\log n)$ 就能查到全局最小值。
这和 Brickwork 里的扫描线"每次只有一个矩形进入/离开 activates 集合"是同一个道理。

和 Brickwork 的对比

	Brickwork（砖墙）	Doorway（门）
消除的维度	扫描 x 坐标，把 2D 矩形重叠问题变成 1D 区间重叠问题	扫描 gap-start 位置，把"多层选位置求交集最大"变成"逐步更新单层 rightend"
事件类型	矩形左边进入（op=1）、右边离开（op=0）	gap-start 出现（更新该层的 rightend）
维护的集合	`set<pair<ll,ll>>` 维护当前所有激活的 y 区间，保证互不重叠	`multiset<ll>` 维护每层当前的 rightend，追踪全局最小值
每次事件的操作	插入时检查前驱/后继是否重叠；删除时直接 erase	更新一层的 rightend（erase 旧值 + insert 新值），查 `*begin()`
核心不变量	activates 中所有区间互不重叠	multiset 中恰好 N 个值，每层一个
判定条件	每次插入都不和邻居重叠 → yes	`*begin() - g` 的最大值就是答案

相同点

都是把高维问题降到一维：Brickwork 把 2D 重叠检测降到 1D 区间检测；Doorway 把"多层 gap 位置选择"降到一维扫描。
每次事件只影响一个元素：Brickwork 每次只有一个区间进/出；Doorway 每次只有一层的 rightend 变化。这是扫描线高效的根本原因。
都依赖有序集合：利用 set/multiset 的 $O(\log n)$ 操作来维护全局信息。

不同点

目标不同：Brickwork 是判定问题（有没有重叠）；Doorway 是最优化问题（最大 opening）。
集合语义不同：Brickwork 的 activates 存的是当前活跃的区间，需要保证互不重叠，所以只需查前驱后继；Doorway 的 multiset 存的是每层一个标量值（rightend），需要的是全局最小值，所以用 begin()。
事件的对称性：Brickwork 有"进入"和"离开"两种事件，是对称的；Doorway 只有一种事件（gap-start），每层的 rightend 只增不减，没有"离开"。

错误的代码（然后采用类似于懒更新的策略。但是呢，要记住一件事情啊，**懒更新**，你不能把更加优秀的东西塞入**这个你的集合里面**）

/**
 * Problem: D. Doorway
 * Contest: 2025
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2181/problem/D
 * Created: 2026-02-10 17:09:28
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define debug3d(a)                                         \
cerr << #a << " = [\n";                                \
for (int i = 0; i < (int)(a).size(); i++)              \
{                                                      \
cerr << "  [\n";                                   \
for (int j = 0; j < (int)(a[i]).size(); j++)       \
{                                                  \
cerr << "    [";                               \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k];     \
cerr << "]\n";                                 \
}                                                  \
cerr << "  ]\n";                                   \
}                                                      \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */
struct Wall_pos {
    ll x1,x2;
};
// struct Event {
//     ll st,ed;
//     // 这里要使用 Auto 的自动推导类型。
//     auto operator<=>(const Event&) const = default;
// };
void Solve() {
    ll N;
    cin >> N;
    vector<vector<ll>> door_mtx(N+2);
    vector<Wall_pos> wall_pos(N+2);
    ll mxx1=0,mnx2=INF;
    for (int i=1;i<=N;++i) {
        ll K,x1,x2;
        cin>>K>>x1>>x2;
        wall_pos[i]={x1,x2};
        mxx1=max(mxx1,x1);
        mnx2=min(mnx2,x2);
        door_mtx[i].resize(K);
        for (auto &v:door_mtx[i]) {
            cin>>v;
        }
    }
    // vector<Event> event_ls;
    map<ll,vector<ll>> event_mtx;
    multiset<ll> ed_st;
    for (int i=1;i<=N;++i) {
        // vector<ll> suf_sum(SZ(door_mtx[i]));
        // partial_sum(door_mtx[i].rbegin(),door_mtx[i].rend(),suf_sum.rbegin());
        // suf_sum.push_back(0);
        ll sum=accumulate(all(door_mtx[i]),0ll);
        auto [x1,x2]=wall_pos[i];
        // event_ls.push_back({x1,x2-sum});
        event_mtx[x1].push_back(x2-sum);
        ed_st.insert(x2-sum);
        ed_st.insert(x2);
        x2-=sum;
        for (auto v:door_mtx[i]) {
            x1+=v;
            x2+=v;
            // event_ls.push_back({x1,x2});
            event_mtx[x1].push_back(x2);
            ed_st.insert(x2);
        }
    }
    ll ans=0;
    for (auto it=event_mtx.begin();it!=event_mtx.end();++it) {
        for (auto ed:it->second) {
            auto it_erase=ed_st.find(ed);
            if (it_erase!=ed_st.end()) {
                ed_st.erase(it_erase);
            }
        }
        if (it->first<mxx1) {
            continue;
        }
        auto nex_it=next(it);
        if (nex_it==event_mtx.end()) {
            continue;
        }
        ll lans=*ed_st.begin()-(nex_it->first);
        ans=max(ans,lans);
    }
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*

*/

for (int i = 1; i <= N; ++i) {
    ll sum = accumulate(all(door_mtx[i]), 0ll);
    auto [x1,x2] = wall_pos[i];
    x2 -= sum;
    // 在没有碰到自己的左端点之前，这个滑动系统不应该贡献任何的这个有效的右端点。
    ri_st.insert(-INF);
    i_ri_ls[i] = -INF;
    x1_idx_x2_mtx[x1].push_back({i, x2});
    for (auto v: door_mtx[i]) {
        x1 += v;
        x2 += v;
        x1_idx_x2_mtx[x1].push_back({i, x2});
    }
}