[BOJ] Journey to TST set1

최근에 PS를 다시 하면서 뭘 풀어야 할지 모르겠다는 생각이 들었다. 둘러보다가 고등학교 친구가 만든 인생추천셋이 있길래 차근차근 풀어보려고 한다.

 

https://dsstar.tistory.com/53

Journey to TST 문제 셋 공유

 

내가 푼 순서대로 리뷰하려고 한다. 때문에 세터의 의도와는 다르게 대략 난이도 순이니 이 부분에 있어서 스포일러를 원치 않는다면 문제를 풀고 오기를 바란다. 약 4.5일간 푼 것 같다. 02/07의 문제셋이다.

 

1. Toilets(17709)

https://www.acmicpc.net/problem/17709

솔직히 여러운 문제는 아니었는데 처음에 조금 생각을 잘못 해서 한 번 틀렸다. 구글 번역으로 문제를 이해할 수 있었다.

그리고 디스크립션이 조금 논란의 여지가 있다.

 

문제

남녀 합쳐 $2N$명이 화장실이 여성 전용 칸, 공용 칸 두 칸밖에 없다. 한 줄로 서서 모두 화장실을 이용하려고 한다. 여성이 선두에 있을 때는 그 선두가 여성 전용, 공용 순으로 빈 칸에 들어가고, 남성이 선두에 있을 때는 공용 칸이 비어있으면 선두가 들어가고 공용 칸이 사용 중이면 여성 중 가장 앞에 있는 사람이 들어간다. 화장실 이용 시간은 1이고 화장실에 들어가는 시간은 없다. 이 때 시간 $N$만에 화장실을 전부 이용하기 위해 줄을 다시 세우려고 한다. 각 사람의 불만도를 기존 줄에서는 뒤에 있었는데 새로운 줄에서는 앞에 있는 사람으로 정의할 때 불만도 최대의 최소를 구하여라. 불가능한 경우 $-1$을 출력하라.

기존 줄은 문자열 $M$개와 $i$번째 문자열 $S_i$가 반복되는 횟수 $K_i$로 표현된다.  ($1 \leq N \leq 10^{18}$, $1 \leq M, \Sigma |S_i| \leq 2 \times 10^5$)

 

풀이

우선 시간 $N$만에 다 사용한다는 건 화장실을 항상 모두 사용 중이라는 이야기다. 때문에 줄을 적절히 바꿔 저 규칙대로 사람을 넣었을 때 못 넣는 경우가 발생하지 않게 하면 된다.

크게 관찰할 사실이 3가지 있다.

 

1. 남성이 $N$명 초과면 불가능, 이하면 가능

각 시간에 남성은 최대 1명씩밖에 못 들어가므로 $N$명 초과면 당연히 불가능. $N$명 이하면 남자를 모두 앞에 세우면 가능.

 

2. 불만도가 최대 $X$인 경우 모든 남성을 전방의 최대 $X$명의 여성을 건너뛰도록 해도 무방하다.

이렇게 해도 불만도가 최대 $X$고 남성을 앞으로 보낼수록 이득인 건 자명하다.

 

3. 여성을 $+1$, 남성을 $-1$로 볼 때 시간 $N$만에 사용 가능한 줄인 것과 (누적합의 최대) - (전체 합) $\leq 1$이 동치다.

(전체합) / $2$가 의미하는 것이 무엇일까? 바로 여성 두 명이 화장실을 동시에 사용해도 되는 총 시간을 말한다. 남성과 여성을 매칭시킨다는 관점에서 보면 (짝수 번째 누적합의 최대)/$2$가 실제로 여성 두 명이 화장실을 사용하는 총 시간이고 시간 $N$만에 사용 가능하려면 이 것이 (전체 합)/$2$와 같아야 함을 알 수 있다. 이 조건과 위 조건이 동치임은 쉽게 알 수 있다.

 

2를 3의 관점에서 본다면 불만도가 최대 $X$라는 것이 누적합의 최대를 $X$ 감소시킬 수 있다는 것을 의미함을 알 수 있다.

 

이러한 사실들을 이용한다면 불가능한 경우 $-1$, 가능한 경우 $\max$($0$, (누적합의 최대) - (전체 합) - $1$)이 답임을 알 수 있다. 시간복잡도는 $O(\Sigma |S_i|)$.

 

코드

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define em emplace

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int MAX = 101010;
const int INF = 1e9;
const ll LINF = 1e18;

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

    ll n;
    cin >> n;
    int m;
    cin >> m;

    ll sum = 0, mx = 0;
    ll len = 0;
    for(int i = 0; i < m; i++) {
        string s; ll k;
        cin >> s >> k;
        ll tmx = 0, num = 0;
        for(int j = 0; j < s.size(); j++) {
            if(s[j] == 'F') num++;
            else num--;
            tmx = max(tmx, num);
        }
        mx = max(mx, sum + max(0LL, num) * (k - 1) + tmx);
        sum += num * k;
    }
    if(sum < 0) cout << "-1\n";
    else cout << max(0LL, mx - 1 - sum) << endl;
}

 

2. Event Hopping(25260)

https://www.acmicpc.net/problem/25260

교육적이면서도 전형적인 문제.

 

문제

$N$개의 이벤트들이 있고 $i$번째 이벤트는 $S_i$에 시작해 $E_i$에 끝난다. $i$번 이벤트에서 $j$번 이벤트로 '전환' 가능하려면 $S_j \leq E_i \leq E_j$여야 한다. $Q$개의 쿼리가 주어지며 각 쿼리에서는 $s$ 이벤트에서 시작해 $e$ 이벤트로 전환하는데 필요한 최소 전환 횟수를 구해야 한다. 불가능한 경우 impossible 출력. ($1 \leq N, Q \leq 10^5$, $1 \leq S_i < E_i \leq 10^9$)

 

풀이

우선 $i$를 고정시키고 어떤 $j$로 이동 가능성을 판단하는 것은 어렵다. $S_j$와 $E_j$가 어떤 범위에 있어야 하는 2D 쿼리가 되기 때문이다. 반면 거꾸로 $j$를 고정시키면 $E_i$가 $S_j$에서 $E_j$ 사이에 있으면 되는 1D 쿼리라 쉽게 판정 가능하다. 따라서 문제를 거꾸로 보고 $e$에서 $s$로 갈 수 있는지로 판별할 것이다.

 

먼저 $x$번 전환 후 다음에 갈 수 있는 이벤트의 $E$ 범위는 하나의 구간으로 표현할 수 있음을 관찰하자. 방금 $j$번 이벤트로 이동을 했다면 다음에 갈 수 있는 $E$ 범위는 원래 범위와 $[S_j, E_j]$의 합집합인데 $E_j$가 원래 범위 안에 있으니 귀납적으로 모두 한 구간임을 볼 수 있다. (그냥 그림 그려보면 더 직관적이다.) 따라서 최적의 이동은 다음으로 이동 가능한 이벤트 $k$들 중 $S_k$가 최소인 것이다.

 

이제 $e$에서 시작해 계속 최적으로 이동하며 탐색 구간에 $E_s$가 들어올 때까지 전환하면 된다. 그런데 각 쿼리마다 일일이 전환시키면 느리다. 여기서 추가적으로 관찰할 사실은 이전 경로와 관계 없이 어떤 전환을 직전에 했다면 다음 최적 전환이 동일하다는 것이다. 만약 그렇지 않다면 이전 상태에서 직전의 전환보다 더 나은 전환이 있었어야 하므로 모순이다. 따라서 각 전환마다 다음 최적 전환을 구한 뒤 스파스 테이블을 이용하면 각 쿼리를 $O(\log N)$만에 처리할 수 있다. 다만 아무리 이동시켜도 도달 못 하는 경우와 $E_s > E_e$인 경우 impossible임에 유의하자.

 

다음 최적 전환을 찾는 것은 세그로 가능하다. 이것과 스파스 테이블 전처리에 $O(N\log N)$, 쿼리처리에 $O(Q\log N)$으로 총 $O((N+Q)\log N)$에 문제를 해결 가능하다.

 

여담으로 처음에 바보같이 스파스 테이블 + 이분탐색을 따로 해서 $O(N\log N+Q\log^2 N)$으로 짰는데도 넉넉하게 맞았다. 이분 탐색과 스파스 테이블은 역시 빠르다.

 

코드

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int MAX = 101010;
const int INF = 1e9;
const ll LINF = 1e18;

struct SEG {
    vector <pii> tree;
    int sz;
    bool base;

    SEG(int n, bool _base = true) : base(_base) {
        sz = 1;
        while(sz < n) sz <<= 1;
        tree.resize(sz<<1);
        for(auto &i : tree) i = pii(INF, 0);
    }

    void update(int k, pii val) {
        int node = k + sz - base;
        tree[node] = min(tree[node], val);
        while(node >>= 1) tree[node] = min(tree[node<<1], tree[node<<1|1]);
    }

    pii cal(int l, int r) {
        pii ret = pii(INF, 0);
        for(l += sz - base, r += sz - base; l <= r; l >>= 1, r >>= 1) {
            if(l & 1) ret = min(ret, tree[l++]);
            if(~r & 1) ret = min(ret, tree[r--]);
        }
        return ret;
    }
};

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

    int n, q;
    cin >> n >> q;
    vector <int> num;
    vector <int> S(n), E(n);

    for(int i = 0; i < n; i++) {
        cin >> S[i] >> E[i];
        num.eb(S[i]), num.eb(E[i]);
    }
    sort(all(num));
    num.erase(unique(all(num)), num.end());

    SEG ST(num.size(), false);
    for(int i = 0; i < n; i++) {
        S[i] = lower_bound(all(num), S[i]) - num.begin();
        E[i] = lower_bound(all(num), E[i]) - num.begin();
        ST.update(E[i], pii(S[i], i));
    }

    vector <int> p[20];
    p[0].resize(n);
    for(int i = 0; i < n; i++) {
        p[0][i] = ST.cal(S[i], E[i]).se;
    }
    for(int i = 1; i < 20; i++) {
        p[i].resize(n);
        for(int j = 0; j < n; j++) {
            p[i][j] = p[i-1][p[i-1][j]];
        }
    }

    while(q--) {
        int s, e;
        cin >> s >> e;
        s--, e--;
        if(s == e) {
            cout << "0\n";
            continue;
        }
        if(E[e] < E[s]) {
            cout << "impossible\n";
            continue;
        }

        int ans = 0, cur = e;
        for(int i = 19; i >= 0; i--) {
            if(S[p[i][cur]] > E[s]) cur = p[i][cur], ans += (1 << i);
        }
        if(S[cur] > E[s]) ans++, cur = p[0][cur];
        if(S[cur] > E[s]) cout << "impossible\n";
        else cout << ans + 1 << '\n';
    }
}

 

3. Solar Lamps(10135)

https://www.acmicpc.net/problem/10135

분명 더 간단한 풀이가 있는데 메모리가 빡빡해서 컷당한다. 메모리가 넉넉해도 시간이 빡빡해서 컷당할 것 같다. 개인적 감상으로 루비급은 아닌 것 같다. (동 티어의 IOI 문제 Rollercoaster Railoads, Friends에 비하면 발상이 훨씬 쉽다고 느꼈다.)

 

문제

램프 $N$개가 2차원 평면에 있다. $i$번째 램프의 좌표는 $(x_i, y_i)$이다. 램프는 모두 동일한 방향과 각도로 빛을 낸다. $i$번째 램프는 시간 $i$에 전력을 공급받아 켜진다. 다만 그 이전에도 $k_i$개의 다른 램프에 빛을 받으면 그 즉시 켜진다. 각 램프에 대해 켜지는 시간을 구하여라. ($1 \leq N \leq 2 \times 10^5$)

 

풀이

우선 램프가 쏘는 두 경계와 수직인 벡터를 적당히 이용하면 좌표변환을 통해 해당 램프 기준 1사분면으로 빛을 내는 것으로 문제로 바꿀 수 있다. (예외가 한 가지 있는데 후술)

 

이 상황에서 문제를 살펴보자. 어떤 $i$번째 램프가 언제 켜지는지 확인하려면 $(x_i, y_i)$ 기준 3사분면의 램프가 언제 켜지는지 알아야 한다. 특히 여기서 $k_i$번째로 늦게 켜지는 램프의 시간과 $i$의 최소가 답이 된다. 순서를 잘 정해서 스위핑하며 k번째 수 쿼리를 (숫자, $y$좌표)의 2D 세그먼트 트리로 적당히 구현해주면 $O(N\log^2 N)$에 답을 구할 수 있다.

 

...그랬다면 좋았을텐데 메모리 이슈로 터진다.

여기서 생각의 전환을 해보자. 그냥 램프들을 나열해놓고 특정 시간 $t$에 켜져 있는 램프들을 모두 구할 수 있을까? 이 질문이 바로 발상의 핵심이다. 여기선 $k$번째 수를 구할 필요가 없다. 스위핑을 한다면 $y$좌표 범위만으로도 번호가 $t$보다 큰 램프들이 켜지는지 판단할 수 있게 된다.(그냥 개수가 $k$값보다 크거나 같은지만 확인하면 되므로)

 

이제 시간 $t$에 켜져 있는 램프들과 안 켜져 있는 램프들을 분리하자. 그리고 시간 $t$에 켜지지 않는 램프들의 $k$ 값을 시간 $t$에 그 램프에 빛을 내는 램프의 총 개수만큼 빼주자. 이렇게 한다면 분리된 시간대의 독립이며 동일한 문제 두 개로 쪼갤 수 있게 된다. 이제 답의 범위를 $[1, N]$에서 시작해 기준 시간을 구간 중앙으로 잡고 점들을 나누며 분할정복을 해주면 총 $O(N\log^2 N)$에 답을 구할 수 있다는 것을 알 수 있다. (DNC optimization과 비슷하게 동 계층에 점 개수 합이 $N$인 점을 이용하면 쉽게 알 수 있다.)

 

여기서 한 가지 예외가 있는데 바로 빛을 직선으로 쏠 때다. (...) 예외처리를 잘 해주자.

 

코드

#include  <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int MAX = 202020;
const int INF = 1e9;
const ll LINF = 1e18;

struct SEG {
    vector <int> tree;
    int sz;
    bool base;

    SEG(int n, bool _base = true) : base(_base) {
        sz = 1;
        while(sz < n) sz <<= 1;
        tree.resize(sz<<1);
    }

    void update(int k, int val) {
        int node = k + sz - base;
        tree[node] += val;
        while(node >>= 1) tree[node] = tree[node<<1] + tree[node<<1|1];
    }

    int cal(int l, int r) {
        int ret = 0;
        for(l += sz - base, r += sz - base; l <= r; l >>= 1, r >>= 1) {
            if(l & 1) ret += tree[l++];
            if(~r & 1) ret += tree[r--];
        }
        return ret;
    }
};
bool flag = false;
void dnc(int s, int e, vector <int> &v, vector <int> &k, vector <int> &ans, vector <pll> &pt, SEG &ST) {
    if(s == e) return;
    int m = s + e >> 1;
    sort(all(v), [&](int a, int b) {
        if(pt[a].fi == pt[b].fi) return pt[a].se < pt[b].se;
        return pt[a].fi < pt[b].fi;
    });
    vector <int> upd, L, R;
    for(int i : v) {
        if(ans[i] > m) {
            int cnt = ST.cal(1, pt[i].se);
            if(flag) cnt = ST.cal(pt[i].se, pt[i].se);
            if(cnt >= k[i]) ans[i] = m;
            else k[i] -= cnt;
        }
        if(ans[i] <= m) {
            ST.update(pt[i].se, 1);
            upd.eb(pt[i].se);
            L.eb(i);
        }
        else R.eb(i);
    }
    for(int i : upd) ST.update(i, -1);
    dnc(s, m, L, k, ans, pt, ST);
    dnc(m+1, e, R, k, ans, pt, ST);
}

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

    int n;
    ll x1, y1, x2, y2;
    cin >> n >> x1 >> y1 >> x2 >> y2;
    if(x1 * y2 - y1 * x2 < 0) swap(x1, x2), swap(y1, y2);
    if(x1 * y2 == y1 * x2) {
        flag = true;
        x2 = -y1, y2 = x1;
    }
    vector <int> k(n+1), ans(n+1), v;
    vector <ll> num;
    vector <pll> pt(n+1);
    for(int i = 1; i <= n; i++) {
        ll x, y; cin >> x >> y;
        pt[i].fi = y2 * x - x2 * y;
        pt[i].se = x1 * y - y1 * x;
        num.eb(pt[i].se);
    }
    sort(all(num));
    num.erase(unique(all(num)), num.end());
    for(int i = 1; i <= n; i++) {
        cin >> k[i];
        v.eb(i);
        pt[i].se = lower_bound(all(num), pt[i].se) - num.begin() + 1;
        ans[i] = i;
    }
    SEG ST(num.size());
    dnc(1, n, v, k, ans, pt, ST);
    for(int i = 1; i <= n; i++) {
        cout << ans[i] << ' ';
    }
    cout << endl;
    return 0;
}

 

4. Fish(5469)

https://www.acmicpc.net/problem/5469

처음 풀이 냈을 때는 난이도가 무슨 다4급이라고 생각했는데 조금씩 생각을 더해가다 보니 적어도 다3급이라는 생각이 들었다.(놓치고 있던 부분이 있었다.) 확실한 건 절대 다1급은 아니라고 생각한다. 정해 철학을 잘 생각해도 미묘한 부분들에서 실수하기 쉬운 게 있긴 한 듯.

 

문제

$F$마리의 물고기가 있고 $K$개의 보석 종류가 있다. $i$번째 물고기는 길이가 $L_i$이며 $C_i$번 보석을 지니고 있다. $2L_i \leq L_j$이면 $j$번 물고기가 $i$번 물고기를 잡아먹을 수 있다. 물고기 한 마리를 골랐을 때 얻을 수 있는 보석 쌍의 개수를 $M$으로 나눈 나머지를 구하여라.

($1 \leq K \leq F \leq 5 \times 10^5$, $1 \leq L_i \leq 10^9$, $1 \leq M \leq 3 \times 10^4$)

 

풀이

관찰할 사실은 크게 2가지이다.

 

1. 같은 종류 보석을 가지고 있는 물고기들 중 가장 긴 물고기만 골라도 충분하다.

자명.

 

2. 1과 같이 고른 물고기들에서 얻을 수 있는 보석 쌍은 '대체로' 그 중에서도 가장 길이가 긴 물고기로부터 얻을 수 있다.

여기서 모호하게 대체로란 말을 썼는데, 이게 이 문제의 핵심이라 그렇다. 만약 어떤 물고기$i$를 고른다 했을 때 길이가 $i$의 절반 이하인 물고기들의 보석 수 합 쌍을 $(S_1, S_2, ..., S_K)$라고 한다면 총 경우의 수는 $\Pi (S_k+1)$이고 그 쌍들은 $k$번째 보석의 개수가 $0$~$S_k$, 다만 $k=C_i$라면 $1$~$S_k+1$인 쌍이다. 그런데 고르는 물고기의 길이가 클수록 $S_k$도 커지니 당연히 '대체로' 포함될 수밖에 없다.

 

1에 해당하는 물고기들을 '유의미한 물고기'라고 하자. 따라서 우리는 유의미한 물고기들에 대해 그것보다 긴 물고기를 고르는 경우에 포함되지 않는 경우를 세서 더하면 된다. 이 것도 2가지로 나누어서 생각할 수 있다. 우선 보석 번호를 해당 보석을 가진 물고기들 중 가장 긴 길이가 증가하는 순으로 다시 붙이자.(그래도 $C_i$라고 하겠다.) $i$번째 물고기를 고른다고 하고 이 물고기가 먹을 수 있는 물고기들의 보석 수 합 쌍을 $(S_1, S_2, ..., S_K)$라 하겠다.

 

1. $k>C_i$인 모든 $k$번 보석이 0개인 경우

이 경우 $\Pi_{k \leq C_i} (S_k + 1)$이다.

 

2. 1이 아니면서 $C_i$번 보석이 $S_{C_i}+1$개인 경우

정확히는 이 중에서 $C_i$번 보석을 $S_{C_i}+1$개 가질 수 있는 유의미한 물고기가 가진 보석들이 0개인 경우이다. 이러한 보석들의 번호는 범위로 나타나며 그 중 가장 작은 보석 번호를 $P_i$라고 하면(없으면 $K+1$) $\Pi_{k<C_i}(S_k+1) \times [\Pi_{C_i<k<P_i}(S_k+1)-1]$이 된다. $P_i$는 ($C_i$번 보석을 가진 물고기들 중 길이 순으로 $S_{C_i}+1$번째 물고기의 길이) $\times$ 2 이상의 길이를 가진 유의미한 물고기들 중 가장 짧은 물고기가 가진 보석 번호이다. 말이 복잡한데 정의를 잘 생각해보면 자명하다.

 

따라서 길이 순으로 정렬 후 훑으면서 주어진 조건을 만족하는 범위를 이분탐색이든 뭐든으로 잘 구해서 더해주면 답을 구할 수 있다. 곱한 값을 구하는 것 등은 세그로 해주면 된다. $O(F\log F)$.

 

2번 조건이 조금 생각하기 까다로울 수 있는데 그냥 한 색마다 뭔가 "빼꼼" 튀어나오고 그걸 잘 예외처리한다고 형상화(?)하면 쉽게 생각할 수 있다. (빼꼼 튀어나와서 0은 불가능하고 튀어나온걸 다른 애가 커버 못하면 따로 세고..)

여담으로 $P_i$를 구하는 과정에서 숫자를 따로 세줘야 되는데 모듈러한 세그 값을 참조하다가 맞왜틀을 여러 번 했다.

 

코드

#include  <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int MAX = 202020;
const int INF = 1e9;
const ll LINF = 1e18;

struct SEG {
    vector <int> tree;
    int sz, mod;
    bool base;
    SEG(int n, int _mod, int x = 0, bool _base = true) : mod(_mod), base(_base) {
        for(sz = 1; sz < n; sz <<= 1) ;
        tree.resize(sz<<1);
        if(x) for(int &i : tree) i = x;
    }

    void update(int x, int val) {
        int node = x + sz - base;
        tree[node] += val;
        tree[node] %= mod;
        while(node >>= 1) {
            tree[node] = (tree[node<<1] * tree[node<<1|1]) % mod;
        }
    }

    int cal(int l, int r) {
        int ret = 1;
        for(l += sz - base, r += sz - base; l <= r; l >>= 1, r >>= 1) {
            if(l & 1) ret = (ret * tree[l++]) % mod;
            if(~r & 1) ret = (ret * tree[r--]) % mod;
        }
        return ret;
    }
};

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

    int n, k, mod;
    cin >> n >> k >> mod;
    vector <pii> F(n), C(k);
    for(int i = 0; i < n; i++) {
        cin >> F[i].fi >> F[i].se;
        C[F[i].se-1].fi = max(C[F[i].se-1].fi, F[i].fi);
    }
    for(int i = 0; i < k; i++) {
        C[i].se = i + 1;
    }
    sort(all(F));
    sort(all(C));
    
    vector <int> num(k+1), cnt(k), tcnt(k), acnt(k);
    vector <vector <int> > L(k);
    SEG ST(k, mod, 1, false);
    for(int i = 0; i < k; i++) {
        num[C[i].se] = i;
    }
    for(int i = 0; i < n; i++) {
        F[i].se = num[F[i].se];
        L[F[i].se].eb(F[i].fi);
        cnt[F[i].se]++;
    }

    int ans = 0, idx = 0;
    for(int i = 0; i < n; i++) {
        tcnt[F[i].se]++;
        while(idx < n && F[idx].fi * 2 <= F[i].fi) {
            ST.update(F[idx].se, 1);
            acnt[F[idx].se]++;
            idx++;
        }
        if(tcnt[F[i].se] == cnt[F[i].se]) {
            ans += ST.cal(0, F[i].se);
            ans %= mod;
            int pos = lower_bound(all(C), pii(2*L[F[i].se][acnt[F[i].se]], 0)) - C.begin();
            ans += ST.cal(0, F[i].se-1) * (ST.cal(F[i].se+1, pos-1) - 1);
            ans = ((ans % mod) + mod) % mod;
        }
    }
    cout << ans << endl;
}