Submission #1191450

#TimeUsernameProblemLanguageResultExecution timeMemory
1191450niepamietamhaslaModern Machine (JOI23_ho_t5)C++20
100 / 100
1880 ms78780 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") int n, m; string s; struct c{ int a; int b; int dod; }; struct d{ vector<c> swapy; }; vector<int> krasnoludki; const int MAXN = 2e5 + 5; const int base = 1 << 17; int ans[MAXN]; d drugaczesc[2 * base]; int M; bool comp(const c &c1, const c &c2){ if(c1.a != c2.a){ return c1.a < c2.a; } return false; } int drugiwyn(int w, int a, int b, int akt_a, int akt_b, int curr){ if(a > b) return curr; if(a <= akt_a and akt_b <= b){ int p = 0; int k = drugaczesc[w].swapy.size() - 1; while(p != k){ int sr = (p + k) / 2; if(drugaczesc[w].swapy[sr].b < curr){ p = sr + 1; } else{ k = sr; } } return (curr + drugaczesc[w].swapy[p].dod) % M; } if(akt_a > b or akt_b < a) return curr; int mid = (akt_a + akt_b) / 2; curr = drugiwyn(2 * w, a, b, akt_a, mid, curr); curr = drugiwyn(2 * w + 1, a, b, mid + 1, akt_b, curr); return curr; } struct e{ int sR; int sB; }; e strzalki[2 * base]; int iloscR(int w, int a, int b, int akt_a, int akt_b){ if(a > b) return 0; if(a <= akt_a and akt_b <= b){ return strzalki[w].sR; } if(akt_a > b or akt_b < a) return 0; int mid = (akt_a + akt_b) / 2; return iloscR(2 * w, a, b, akt_a, mid) + iloscR(2 * w + 1, a, b, mid + 1, akt_b); } int iloscB(int w, int a, int b, int akt_a, int akt_b){ if(a > b) return 0; if(a <= akt_a and akt_b <= b){ return strzalki[w].sB; } if(akt_a > b or akt_b < a) return 0; int mid = (akt_a + akt_b) / 2; return iloscB(2 * w, a, b, akt_a, mid) + iloscB(2 * w + 1, a, b, mid + 1, akt_b); } int ktaB(int w, int akt_a, int akt_b, int curr, int cel){ if(akt_a == akt_b) return akt_a; int mid = (akt_a + akt_b) / 2; if(strzalki[2 * w].sB + curr < cel){ return ktaB(2 * w + 1, mid + 1, akt_b, curr + strzalki[2 * w].sB, cel); } else{ return ktaB(2 * w, akt_a, mid, curr, cel); } } int ktaR(int w, int akt_a, int akt_b, int curr, int cel){ if(akt_a == akt_b) return akt_a; int mid = (akt_a + akt_b) / 2; if(strzalki[2 * w + 1].sR + curr < cel){ return ktaR(2 * w, akt_a, mid, curr + strzalki[2 * w + 1].sR, cel); } else{ return ktaR(2 * w + 1, mid + 1, akt_b, curr, cel); } } pair<int,int> dodajp(int pref, int suff, int ile, int n){ if(ile == 0) return {pref, suff}; int pocz = pref; int kon = n - suff + 1; int v = iloscB(1, pocz + 1, kon - 1, 1, base); if(ile >= v){ pocz = kon - 1; ile -= v; pocz = (pocz + ile) % M; kon = pocz + 1; return {pocz, n - pocz}; } v = iloscB(1, 1, pocz, 1, base); return {ktaB(1, 1, base, 0, v + ile + 1) - 1, suff}; } pair<int,int> dodajk(int pref, int suff, ll ile, int n){ if(ile == 0) return {pref, suff}; int pocz = pref; int kon = n - suff + 1; int v = iloscR(1, pocz + 1, kon - 1, 1, base); //cout << pocz << " " << kon << " pk\n"; //cout << ile << " " << v << " il\n"; if(ile >= v){ //cout << suff << " " << ile + 1 << " si\n"; ile -= v; //cout << pocz << " " << ile << " pi\n"; pocz = (pocz - ile + 2 * M) % M; return {pocz, n - pocz}; } v = iloscR(1, kon, base, 1, base); return {pocz, n - ktaR(1, 1, base, 0, v + ile + 1)}; } pair<int,int> dodajs(int pref, int suff, int mid, int n){ int pocz = pref; int kon = n - suff + 1; int iR1 = pref; int iR2 = iloscR(1, pocz + 1, mid - 1, 1, base); int iB1 = suff; int iB2 = iloscB(1, mid + 1, kon - 1, 1, base); int s1 = iR1 + iR2; int s2 = iB1 + iB2; //cout << s1 << " " << s2 << " s\n"; //cout << iB1 << " " << iB2 << " iB\n"; if(s1 >= s2){ if(s2 >= iR2){ pocz = pref - (s2 - iR2); return {pocz, n - pocz}; } else{ int v = iloscR(1, mid, base, 1, base); return {pocz, n - ktaR(1, 1, base, 0, v + s2 + 1)}; } } else{ if(s1 + 1 >= iB2){ pocz = kon - 1 + (s1 - iB2 + 1); return {pocz, n - pocz}; } else{ int v = iloscB(1, 1, mid, 1, base); return {ktaB(1, 1, base, 0, v + s1 + 2) - 1, suff}; } } } struct zap{ int pref; int suff; int org; int a; int b; }; vector<zap> queries; vector<zap> nowe; struct d2{ int sumaakt; int sumanieakt; int minimalny; }; d2 drzew[2 * base]; vector<int> wylacz[MAXN]; const int INF = 1e9; void cofnij(){ for(int i = 1; i <= m; ++i){ drzew[i + base - 1] = {n - krasnoludki[i], 0, krasnoludki[i]}; } for(int i = base - 1; i > 0; --i){ drzew[i].sumaakt = drzew[2 * i].sumaakt + drzew[2 * i + 1].sumaakt; drzew[i].sumanieakt = drzew[2 * i].sumanieakt + drzew[2 * i + 1].sumanieakt; drzew[i].minimalny = min(drzew[2 * i].minimalny, drzew[2 * i + 1].minimalny); } return; } bool comp2(const zap &z1, const zap &z2){ if(z1.pref != z2.pref){ return z1.pref < z2.pref; } return false; } void akt(int w){ w += base - 1; drzew[w] = {0, krasnoludki[w - base + 1], INF}; w /= 2; while(w != 0){ drzew[w].sumaakt = drzew[2 * w].sumaakt + drzew[2 * w + 1].sumaakt; drzew[w].sumanieakt = drzew[2 * w].sumanieakt + drzew[2 * w + 1].sumanieakt; drzew[w].minimalny = min(drzew[2 * w].minimalny, drzew[2 * w + 1].minimalny); w /= 2; } return; } int znajdz(int w, int akt_a, int akt_b, int granica){ if(akt_a == akt_b) return akt_a; int mid = (akt_a + akt_b) / 2; //cout << w << " " << drzew[2 * w].minimalny << " " << drzew[2 * w + 1].minimalny << " d\n"; //cout << granica << " granica\n"; if(drzew[2 * w].minimalny < granica){ return znajdz(2 * w, akt_a, mid, granica); } else{ return znajdz(2 * w + 1, mid + 1, akt_b, granica); } return -1; } int znajdzsrodek(int w, int a, int b, int akt_a, int akt_b, int granica){ //cout << w << " " << a << " " << b << " " << akt_a << " " << akt_b << " " << granica << " drzewo\n"; if(a <= akt_a and akt_b <= b){ //cout << w << " " << drzew[w].minimalny << " " << granica << " oblsr\n"; //cout << "#\n"; //cout << drzew[w].minimalny << " " << granica << " gr\n"; if(drzew[w].minimalny >= granica) return -1; else return znajdz(w, akt_a, akt_b, granica); } if(akt_a > b or akt_b < a) return -1; int mid = (akt_a + akt_b) / 2; int v1 = znajdzsrodek(2 * w, a, b, akt_a, mid, granica); if(v1 != -1) return v1; else return znajdzsrodek(2 * w + 1, a, b, mid + 1, akt_b, granica); } struct trzy{ int pref; int suff; int ind; }; trzy szuk; bool czy(int pref, int suff, int ile1, int ile2){ int pocz = pref; int kon = n - suff + 1; int v = iloscB(1, pocz + 1, kon - 1, 1, base); if(ile1 > v) return false; v = iloscB(1, 1, pocz, 1, base); pref = ktaB(1, 1, base, 0, v + ile1 + 1) - 1; v = iloscR(1, pocz + 1, kon - 1, 1, base); if(ile2 > v) return false; return true; } int aktpref; int aktsuff; int ostatni(int w, int akt_a, int akt_b){ if(akt_a == akt_b) { szuk.pref += drzew[w].sumanieakt; szuk.suff += drzew[w].sumaakt; return akt_a; } int mid = (akt_a + akt_b) / 2; if(czy(aktpref, aktsuff, szuk.pref + drzew[2 * w].sumanieakt, szuk.suff + drzew[2 * w].sumaakt)){ szuk.pref += drzew[2 * w].sumanieakt; szuk.suff += drzew[2 * w].sumaakt; return ostatni(2 * w + 1, mid + 1, akt_b); } else{ return ostatni(2 * w, akt_a, mid); } } int znajdzostatni(int w, int a, int b, int akt_a, int akt_b){ if(a > b){ szuk = {0, 0, b}; return b; } if(a <= akt_a and akt_b <= b){ if(czy(aktpref, aktsuff, szuk.pref + drzew[w].sumanieakt, szuk.suff + drzew[w].sumaakt) == true){ szuk.pref += drzew[w].sumanieakt; szuk.suff += drzew[w].sumaakt; return -1; } else{ int t = ostatni(w, akt_a, akt_b); szuk.ind = t; return t; } } if(akt_a > b or akt_b < a) return -1; int mid = (akt_a + akt_b) / 2; auto v1 = znajdzostatni(2 * w, a, b, akt_a, mid); if(v1 != -1) return v1; auto v2 = znajdzostatni(2 * w + 1, a, b, mid + 1, akt_b); return v2; } pair<int,int> suma(int w, int a, int b, int akt_a, int akt_b){ if(a <= akt_a and akt_b <= b){ return {drzew[w].sumanieakt, drzew[w].sumaakt}; } if(akt_b < a or akt_a > b) return {0, 0}; int mid = (akt_a + akt_b) / 2; auto u1 = suma(2 * w, a, b, akt_a, mid); auto u2 = suma(2 * w + 1, a, b, mid + 1, akt_b); return {u1.first + u2.first, u1.second + u2.second}; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; M = n + 1; int a, b; cin >> s; int p1 = 0; int s1 = 0; for(int i = 0; i < n; ++i){ if(s[i] == '>' or s[i] == 'R'){ p1++; } else{ break; } } for(int i = n - 1; i >= 0; --i){ if(s[i] == '<' or s[i] == 'B'){ s1++; } else{ break; } } //liczenie drzewa strzalek { for(int i = 0; i < n; ++i){ if(s[i] == '>' or s[i] == 'R'){ strzalki[i + base] = {1, 0}; } else{ strzalki[i + base] = {0, 1}; } } for(int i = base - 1; i > 0; --i){ strzalki[i] = {strzalki[2 * i].sR + strzalki[2 * i + 1].sR, strzalki[2 * i].sB + strzalki[2 * i + 1].sB}; } } //liczenie 2 czesci { krasnoludki.push_back(-1); for(int i = 0; i < m; ++i){ cin >> a; krasnoludki.push_back(a); drugaczesc[i + base].swapy = {{0, a - 1, a + 1}, {a, n, a}}; } for(int i = m + base; i < 2 * base; ++i){ drugaczesc[i].swapy = {{0, n, 0}}; } for(int i = base - 1; i > 0; --i){ //cout << i << " i\n"; auto v1 = drugaczesc[2 * i].swapy; auto v2 = drugaczesc[2 * i + 1].swapy; vector<c> odp; auto policz = [&](int a, int b, int dod){ int p = 0; int k = v2.size() - 1; while(p != k){ int sr = (p + k) / 2; if(v2[sr].b < a){ p = sr + 1; } else{ k = sr; } } if(v2[p].a <= a and b <= v2[p].b){ //cout << (a - dod + 5 * M) % M << " " << (b - dod + 5 * M) % M << " " << dod + v2[p].dod << " if1\n"; odp.push_back({(a - dod + 5 * M) % M, (b - dod + 5 * M) % M, dod + v2[p].dod}); return; } //cout << a << " " << b << " ab\n"; int curr = p; //cout << (a - dod + 5 * M) % M << " " << (v2[curr].b - dod + 5 * M) % M << " " << dod + v2[curr].dod << " lewo\n"; odp.push_back({(a - dod + 5 * M) % M, (v2[curr].b - dod + 5 * M) % M, dod + v2[curr].dod}); curr++; while(v2[curr].a <= b){ if(v2[curr].b <= b){ //cout << (v2[curr].a - dod + 5 * M) % M << " " << (v2[curr].b - dod + 5 * M) % M << " " << dod + v2[curr].dod << " mid\n"; odp.push_back({(v2[curr].a - dod + 5 * M) % M, (v2[curr].b - dod + 5 * M) % M, dod + v2[curr].dod}); } else{ //cout << (v2[curr].a - dod + 5 * M) % M << " " << (b - dod + 5 * M) % M << " " << dod + v2[curr].dod << " prawo\n"; odp.push_back({(v2[curr].a - dod + 5 * M) % M, (b - dod + 5 * M) % M, dod + v2[curr].dod}); break; } if(curr == v2.size() - 1) break; curr++; } return; }; for(auto u : v1){ int valdod = (u.a + u.dod) % M; int valkon = (u.b + u.dod) % M; //cout << valdod << " " << valkon << " pk\n"; if(valdod <= valkon){ policz(valdod, valkon, u.dod); } else{ policz(valdod, n, u.dod); policz(0, valkon, u.dod); } } vector<c> tmp; for(auto u : odp){ if(u.a > u.b){ tmp.push_back({0, u.b, u.dod}); tmp.push_back({u.a, n, u.dod}); } else{ tmp.push_back(u); } tmp.back().dod %= M; } odp = tmp; // for(auto u : odp){ // cout << u.a << " " << u.b << " " << u.dod << " po zlozeniu\n"; // } sort(odp.begin(),odp.end(),comp); drugaczesc[i].swapy = odp; } } for(int i = 1; i <= m; ++i){ wylacz[krasnoludki[i]].push_back(i); } for(int i = base + m; i < 2 * base; ++i){ drzew[i] = {0, 0, INF}; } int q; cin >> q; for(int i = 0; i < q; ++i){ cin >> a >> b; if(p1 + s1 == n){ ans[i] = drugiwyn(1, a, b, 1, base, p1); } else{ queries.push_back({p1, s1, i, a, b}); } } cofnij(); while(queries.size() > 0){ sort(queries.begin(),queries.end(), comp2); // for(auto u : queries){ // cout << u.pref << " " << u.suff << " zapytanie\n"; // } int it = 0; for(int i = 0; i <= n; ++i){ if(it == queries.size()) break; for(auto u : wylacz[i]){ //cout << u << " " << krasnoludki[u] << " wylaczyc\n"; akt(u); } while(it < queries.size() and queries[it].pref == i){ // for(int i = 1; i < 2 * base; ++i){ // cout << i << " " << drzew[i].minimalny << " mi\n"; // } //cout << queries[it].a << " " << queries[it].b << " przedzial\n"; int ktory = znajdzsrodek(1, queries[it].a, queries[it].b, 1, base, n - queries[it].suff + 1); if(ktory == -1){ pair<int,int> tmp = {queries[it].pref, queries[it].suff}; if(krasnoludki[queries[it].a] <= tmp.first){ tmp = dodajp(tmp.first, tmp.second, krasnoludki[queries[it].a], n); } else{ tmp = dodajk(tmp.first, tmp.second, n - krasnoludki[queries[it].a], n); } if(tmp.first + tmp.second == n){ ans[queries[it].org] = drugiwyn(1, queries[it].a + 1, queries[it].b, 1, base, tmp.first); } else{ szuk = {0, 0, -1}; aktpref = queries[it].pref; aktsuff = queries[it].suff; znajdzostatni(1, queries[it].a, queries[it].b, 1, base); if(szuk.ind == -1) szuk.ind = queries[it].b; trzy ile = szuk; //cout << ile.ind << " il\n"; pair<int,int> p = {queries[it].pref, queries[it].suff}; if(ile.ind == queries[it].b){ p = dodajp(p.first, p.second, ile.pref, n); p = dodajk(p.first, p.second, ile.suff, n); int kon = n - p.second + 1; ans[queries[it].org] = p.first + iloscR(1, p.first + 1, kon - 1, 1, base); } else{ p = dodajp(p.first, p.second, ile.pref, n); p = dodajk(p.first, p.second, ile.suff, n); ile.ind++; if(krasnoludki[ile.ind] <= p.first){ p = dodajp(p.first, p.second, krasnoludki[ile.ind], n); } else{ p = dodajk(p.first, p.second, n - krasnoludki[ile.ind], n); } ans[queries[it].org] = drugiwyn(1, ile.ind + 1, queries[it].b, 1, base, p.first); } } } else{ if(ktory == queries[it].a){ //cout << "#\n"; pair<int,int> p = {queries[it].pref, queries[it].suff}; p = dodajs(p.first, p.second, krasnoludki[queries[it].a], n); if(queries[it].a == queries[it].b){ int kon = n - p.second + 1; ans[queries[it].org] = p.first + iloscR(1, p.first + 1, kon - 1, 1, base); } else if(p.first + p.second == n){ ans[queries[it].org] = drugiwyn(1, queries[it].a + 1, queries[it].b, 1, base, p.first); } else{ //cout << p.first << " " << p.second << " nowe\n"; nowe.push_back({p.first, p.second, queries[it].org, queries[it].a + 1, queries[it].b}); } } else{ pair<int,int> tmp = {queries[it].pref, queries[it].suff}; if(krasnoludki[queries[it].a] <= tmp.first){ tmp = dodajp(tmp.first, tmp.second, krasnoludki[queries[it].a], n); } else{ tmp = dodajk(tmp.first, tmp.second, n - krasnoludki[queries[it].a], n); } if(tmp.first + tmp.second == n){ ans[queries[it].org] = drugiwyn(1, queries[it].a + 1, queries[it].b, 1, base, tmp.first); } else{ pair<int,int> dod = suma(1, queries[it].a, ktory - 1, 1, base); if(czy(queries[it].pref, queries[it].suff, dod.first, dod.second)){ szuk = {dod.first, dod.second, ktory-1}; } else{ szuk = {0, 0, -1}; aktpref = queries[it].pref; aktsuff = queries[it].suff; znajdzostatni(1, queries[it].a, ktory - 1, 1, base); } if(szuk.ind == -1) szuk.ind = ktory - 1; trzy ile = szuk; pair<int,int> p = {queries[it].pref, queries[it].suff}; //cout << ile.pref << " " << ile.suff << " " << ile.ind << " ile\n"; if(ile.ind != ktory - 1){ p = dodajp(p.first, p.second, ile.pref, n); p = dodajk(p.first, p.second, ile.suff, n); ile.ind++; if(krasnoludki[ile.ind] <= p.first){ p = dodajp(p.first, p.second, krasnoludki[ile.ind], n); } else{ p = dodajk(p.first, p.second, n - krasnoludki[ile.ind], n); } ans[queries[it].org] = drugiwyn(1, ile.ind + 1, queries[it].b, 1, base, p.first); } else{ p = dodajp(p.first, p.second, ile.pref, n); p = dodajk(p.first, p.second, ile.suff, n); ile.ind++; if(krasnoludki[ile.ind] <= p.first){ p = dodajp(p.first, p.second, krasnoludki[ile.ind], n); } else if(krasnoludki[ile.ind] > n - p.second){ p = dodajk(p.first, p.second, n - krasnoludki[ile.ind], n); } else{ p = dodajs(p.first, p.second, krasnoludki[ile.ind], n); } //cout << p.first << " " << p.second << " nowa\n"; if(ile.ind == queries[it].b){ int kon = n - p.second + 1; ans[queries[it].org] = p.first + iloscR(1, p.first + 1, kon - 1, 1, base); } else if(p.first + p.second == n){ ans[queries[it].org] = drugiwyn(1, ile.ind + 1, queries[it].b, 1, base, p.first); } else{ nowe.push_back({p.first, p.second, queries[it].org, ile.ind + 1, queries[it].b}); } } } } } ++it; } } queries = nowe; nowe.clear(); cofnij(); } for(int i = 0; i < q; ++i){ cout << ans[i] << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...