# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1239289 | faruk | Crossing (JOI21_crossing) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
using namespace std;
typedef __uint128_t ll;
typedef pair<ll, ll> pii;
const ll P = 23;
const ll mod2 = 1e16 + 7;
const ll mod1 = 1e15 + 9;
const ll maxn = 3e5;
ll merge(ll l, ll r, ll v1, ll v2, ll mod, vector<ll> &powp) {
return ((powp.at(r - l + 1) * v2) % mod + v1) % mod;
}
map<char, ll> trans = {{'J', 43}, {'O', 39}, {'I', 53}};
struct seggy {
ll mod;
ll n;
vector<ll> seg, lazy, powp, csum;
seggy() {}
seggy(ll n, ll mod) : mod(mod), n(n), seg(vector<ll>(4 * n)), lazy(vector<ll>(4 * n)) {
powp = csum = vector<ll>(maxn, 1);
for (ll i = 1; i < maxn; i++)
powp.at(i) = powp.at(i - 1) * P % mod;
csum.at(0) = 0;
for (ll i = 2; i < maxn; i++)
csum.at(i) = (csum.at(i - 1) + po