제출 #1188703

#제출 시각아이디문제언어결과실행 시간메모리
1188703niepamietamhaslaModern Machine (JOI23_ho_t5)C++20
62 / 100
2582 ms184608 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; 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){ 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){ 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 Node{ ll suma; ll ile; Node *l, *r; Node(ll x, ll y) : ile(x), suma(y), l(nullptr), r(nullptr) {} Node(Node *ll, Node *rr) : ile(ll->ile + rr->ile), suma(ll->suma + rr->suma), l(ll), r(rr) {} }; Node *roots[MAXN]; Node *build(int akt_a = 1, int akt_b = base){ if(akt_a == akt_b) return new Node(0ll, 0ll); int mid = (akt_a + akt_b) / 2; return new Node(build(akt_a, mid), build(mid + 1, akt_b)); } Node *add(Node *prev, ll val, int akt_a = 1, int akt_b = base){ if(akt_a == akt_b) return new Node(prev->ile + 1, prev->suma + val); int mid = (akt_a + akt_b) / 2; if(val <= mid){ return new Node(add(prev->l, val, akt_a, mid), prev->r); } else{ return new Node(prev->l, add(prev->r, val, mid + 1, akt_b)); } } pair<ll,ll> oblicz(Node *k, Node*p, int a, int b, int akt_a, int akt_b){ if(a <= akt_a and akt_b <= b){ return {k->ile - p->ile, k->suma - p->suma}; } if(akt_a > b or akt_b < a) return {0ll, 0ll}; int mid = (akt_a + akt_b) / 2; auto v1 = oblicz(k->l, p->l, a, b, akt_a, mid); auto v2 = oblicz(k->r, p->r, a, b, mid + 1, akt_b); return {v1.first + v2.first, v1.second + v2.second}; } pair<ll,ll> obl(int k, int p, int a, int b){ //cout << p << " " << k << " przedzial\n"; //cout << a << " " << b << " wartosci\n"; return oblicz(roots[k], roots[p-1], a, b, 1, base); } int isans[MAXN]; vector<int> wlacz[MAXN]; vector<int> wylacz[MAXN]; array<int, 3> updejt[MAXN]; set<array<int, 3>> curr; int koniec[MAXN]; bool czy(int pref, int suff, ll ile1, ll ile2, int n){ 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 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; } } //liczenie trwalego drzewa ilosci elementu roots[0] = build(); for(int i = 1; i <= m; ++i){ roots[i] = add(roots[i - 1], krasnoludki[i]); //cout << roots[i]->ile << " " << roots[i]->suma << " " << i << " roots\n"; } 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}); } } while(queries.size() > 0){ //cout << queries.size() << " sajz\n"; for(int i = 0; i < queries.size(); ++i){ //cout << queries[i].a << " " << queries[i].b << " ab\n"; wlacz[queries[i].a].push_back(i); wylacz[queries[i].b].push_back(i); isans[i] = 0; updejt[i][2] = -1; koniec[i] = -1; } for(int i = 1; i <= m; ++i){ for(auto u : wlacz[i]){ curr.insert({queries[u].pref + 1, n - queries[u].suff, u}); } wlacz[i].clear(); while(curr.size() > 0){ //cout << (*curr.begin())[0] << " " << (*curr.begin())[1] << " pierw\n"; auto it = curr.upper_bound({krasnoludki[i] + 1, 0, 0}); if(it == curr.begin()) break; --it; if((*it)[0] > krasnoludki[i] or (*it)[1] < krasnoludki[i]) break; //cout << "wej\n"; int nr = (*it)[2]; isans[nr] = 1; updejt[nr][2] = krasnoludki[i]; updejt[nr][0] = obl(i - 1, queries[nr].a, 1, queries[nr].pref).second; auto t = obl(i - 1, queries[nr].a, n - queries[nr].suff + 1, base); updejt[nr][1] = (n * t.first - t.second); //cout << i << " i\n"; koniec[nr] = i; //cout << nr << " ustaw koniec\n"; curr.erase(it); } //cout << krasnoludki[i] << " dod\n"; for(auto u : wylacz[i]){ //cout << koniec[u] << " koniec\n"; if(isans[u] == 1) continue; //cout << u << " nr\n"; //cout << "#\n"; updejt[u][2] = -1; auto l = obl(i, queries[u].a, 1, queries[u].pref); //cout << l.first << " " << l.second << " l\n"; updejt[u][0] = l.second; auto t = obl(i, queries[u].a, n - queries[u].suff + 1, base); updejt[u][1] = (n * t.first - t.second); curr.erase({queries[u].pref + 1, n - queries[u].suff, u}); koniec[u] = queries[u].b; } wylacz[i].clear(); } curr.clear(); //cout << "po\n"; for(int i = 0; i < queries.size(); ++i){ //cout << updejt[i][0] << " " << updejt[i][1] << " " << updejt[i][2] << " update\n"; pair<int,int> p = {queries[i].pref, queries[i].suff}; //cout << p.first << " " << p.second << " ps\n"; //cout << updejt[i][0] << " " << updejt[i][1] << " upd\n"; if(czy(p.first, p.second, updejt[i][0], updejt[i][1], n) == false){ //cout << "#\n"; pair<int,int> tmp; if(krasnoludki[queries[i].a] <= p.first){ tmp = dodajp(p.first, p.second, krasnoludki[queries[i].a], n); } else{ tmp = dodajk(p.first, p.second, n - krasnoludki[queries[i].a], n); } if(tmp.first + tmp.second == n){ ans[queries[i].org] = drugiwyn(1, queries[i].a + 1, queries[i].b, 1, base, tmp.first); continue; } int pocz = queries[i].a; int kon = koniec[i]; while(pocz != kon){ int sr = (pocz + kon + 1) / 2; auto pr = obl(sr, queries[i].a, 1, p.first); auto su = obl(sr, queries[i].a, n - p.second + 1, base); if(czy(p.first, p.second, pr.second, n * su.first - su.second, n)){ pocz = sr; } else{ kon = sr - 1; } } auto pu = obl(pocz, queries[i].a, 1, p.first); auto su = obl(pocz, queries[i].a, n - p.second + 1, base); p = dodajp(p.first, p.second, pu.second, n); p = dodajk(p.first, p.second, n * su.first - su.second, n); if(krasnoludki[pocz + 1] <= p.first){ p = dodajp(p.first, p.second, krasnoludki[pocz + 1], n); } else{ p = dodajk(p.first, p.second, n - krasnoludki[pocz + 1], n); } ans[queries[i].org] = drugiwyn(1, pocz + 2, queries[i].b, 1, base, p.first); continue; } if(updejt[i][2] == -1){ p = dodajp(p.first, p.second, updejt[i][0], n); //cout << p.first << " " << p.second << " po pocz\n"; //cout << updejt[i][1] << " u1\n"; p = dodajk(p.first, p.second, updejt[i][1], n); //cout << p.first << " " << p.second << " po obu\n"; if(p.first + p.second == n){ ans[queries[i].org] = p.first; } else{ int pocz = p.first; int kon = n - p.second + 1; ans[queries[i].org] = p.first + iloscR(1, pocz + 1, kon - 1, 1, base); } } else{ p = dodajp(p.first, p.second, updejt[i][0], n); //cout << p.first << " " << p.second << " po pocz\n"; p = dodajk(p.first, p.second, updejt[i][1], n); //cout << p.first << " " << p.second << " po kon\n"; if(updejt[i][2] <= p.first){ p = dodajp(p.first, p.second, updejt[i][2], n); } else if(updejt[i][2] > n - p.second){ p = dodajk(p.first, p.second, n - updejt[i][2], n); } else{ p = dodajs(p.first, p.second, updejt[i][2], n); } //cout << p.first << " " << p.second << " po mid\n"; if(koniec[i] == queries[i].b){ if(p.first + p.second == n){ ans[queries[i].org] = p.first; } else{ int pocz = p.first; int kon = n - p.second + 1; ans[queries[i].org] = p.first + iloscR(1, pocz + 1, kon - 1, 1, base); } } else if(p.first + p.second == n){ ans[queries[i].org] = drugiwyn(1, koniec[i] + 1, queries[i].b, 1, base, p.first); } else{ //cout << p.first << " " << p.second << " po srodku\n"; nowe.push_back({p.first, p.second, queries[i].org, koniec[i] + 1, queries[i].b}); } } } queries = nowe; nowe.clear(); } 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...