Submission #1262523

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262523		M_W_13	Modern Machine (JOI23_ho_t5)	C++20	100 / 100	865 ms	188984 KiB

Main

#include <bits/stdc++.h>

using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); i++)
typedef long long ll;
#define st first
#define nd second
#define pb push_back
const ll MAXN = 1 << 17;
const ll MAXK = 20;
ll maksmale[MAXN][MAXK];
ll minduze[MAXN][MAXK];
ll sumamale[MAXN][MAXK];
ll sumaduze[MAXN][MAXK];
ll gdziep[MAXN];
ll gdziel[MAXN];
ll ilewprawo[MAXN];
ll ilewlewo[MAXN];

struct trojka {
	ll l, r;
	ll a;
};

vector<trojka> seg[2 * MAXN];

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	gdziel[0] = -1;
	gdziep[0] = MAXN - 1;
    ll n, m;
	cin >> n >> m;
	string s;
	cin >> s;
	ll t = 0;
	ll ktp = 0;
	ll ktl = 0;
	rep(i, n) {
		if (s[i] == 'R') {
			ktp++;
			t++;
		}
		else {
			ktl++;
			gdziel[ktl] = i;
		}
		ilewlewo[i] = ktl;
		ilewprawo[i] = ktp;
	}
	ktp = 0;
	for (ll i = n - 1; i >= 0; i--) {
		if (s[i] == 'R') {
			ktp++;
			gdziep[ktp] = i;
		}
	}
	ll lewbaza = 0;
	while (lewbaza < n && s[lewbaza] == 'R') {
		lewbaza++;
	}
	ll prawbaza = n - 1;
	while (prawbaza >= 0 && s[prawbaza] == 'B') {
		prawbaza--;
	}









	
	ll T[m];
	ll polow = n/2;
	rep(i, m) {
		cin >> T[i];
		if (T[i] <= polow) {
			sumamale[i][0] += T[i];
			maksmale[i][0] = T[i];
			minduze[i][0] = n + 5;
		}
		else {
			sumaduze[i][0] += (n - T[i]);
			maksmale[i][0] = -1;
			minduze[i][0] = T[i];
		}
		ll v = i + MAXN;
		seg[v].pb({0, T[i] - 1, T[i] + 1});
		seg[v].pb({T[i], n, T[i]});
	}












	for (ll k = 1; k < MAXK; k++) {
		ll ile = (1 << (k - 1));
		rep(i, m) {
			if (i + ile >= m) {
				sumamale[i][k] = sumamale[i][k - 1];
				sumaduze[i][k] = sumaduze[i][k - 1];
				maksmale[i][k] = maksmale[i][k - 1];
				minduze[i][k] = minduze[i][k - 1];
			}
			else {
				sumamale[i][k] = sumamale[i][k - 1] + sumamale[i + ile][k - 1];
				sumaduze[i][k] = sumaduze[i][k - 1] + sumaduze[i + ile][k - 1];
				maksmale[i][k] = max(maksmale[i][k - 1], maksmale[i + ile][k - 1]);
				minduze[i][k] = min(minduze[i][k - 1], minduze[i + ile][k - 1]);
			}
		}
	}









	
	for (ll i = m; i < MAXN; i++) {
		seg[i + MAXN].push_back({0, n, 0});
	}
	for (ll v = MAXN - 1; v >= 1; v--) {
		vector<trojka> baza;
		for (auto troj: seg[2 * v]) {
			ll l = (troj.l + troj.a) % (n + 1);
			ll r = (troj.r + troj.a) % (n + 1);
			if (l > r) {
				ll kt = n;
				ll ile = kt - l;
				baza.pb({troj.l, troj.l + ile, troj.a});
				baza.pb({troj.l + ile + 1, troj.r, troj.a});
			}
			else {
				baza.pb(troj);
			}
		}
		for (auto troj: baza) {
			ll l = (troj.l + troj.a) % (n + 1);
			ll r = (troj.r + troj.a) % (n + 1);
			ll sz = seg[2 * v + 1].size();
			ll poc = 0;
			ll kon = sz;
			ll odp = sz;
			while (poc < kon) {
				ll sr = (poc + kon)/2;
				if (seg[2 * v + 1][sr].l > l) {
					kon = sr;
				}
				else {
					poc = sr + 1;
					odp = sr;
				}
			}
			ll it = odp;
			while (it < sz && seg[2 * v + 1][it].l <= r) {
				ll wspl = max(l, seg[2 * v + 1][it].l);
				ll wspr = min(r, seg[2 * v + 1][it].r);
				ll jakie = seg[2 * v + 1][it].a;
				seg[v].pb({troj.l + wspl - l, troj.l + wspr - l, (jakie + troj.a) % (n + 1)});
				it++;
			}
		}
	}
	// for (auto troj: seg[1]) {
	// 	cout << troj.l << " " << troj.r << " " << troj.a << '\n';
	// }





















	ll z;
	cin >> z;
	while (z--) {
		ll l, r;
		cin >> l >> r;
		







		l--;
		r--;
		ll jakiet = 0;
		ll lew = lewbaza;
		ll praw = prawbaza;
		bool czykonc = false;
		while (lew <= praw) {
            // cout << "lew = " << lew << " praw = " << praw << " 33" << '\n';
			ll liczbawlewo = ilewlewo[praw];
			if (lew - 1 >= 0) {
				liczbawlewo -= ilewlewo[lew - 1];
			}
			ll liczbawprawo = ilewprawo[praw];
			if (lew - 1 >= 0) {
				liczbawprawo -= ilewprawo[lew - 1];
			}
			ll it = l;
			ll k = MAXK - 1;
			ll przedwlewo = 0;
			if (lew > 0) {
				przedwlewo = ilewlewo[lew - 1];
			}
			ll zaprawo = ilewprawo[n - 1];
			if (praw >= 0) {
				zaprawo -= ilewprawo[praw];
			}
			ll sumamalych = 0;
			ll sumaduzych = 0;
			while  (k >= 0) {
				if (((it + (1 << k) - 1) > r) || maksmale[it][k] > lew || minduze[it][k] <= praw + 1 || sumamale[it][k] + sumamalych >= liczbawlewo || sumaduze[it][k] + sumaduzych >= liczbawprawo) {

				}
				else if (max(lew, gdziel[sumamale[it][k] + sumamalych + przedwlewo] + 1) >= min(praw, gdziep[sumaduze[it][k] + sumaduzych + zaprawo] - 1)) {

				}
				else {
					sumamalych += sumamale[it][k];
                    // cout << "it = " << it << " k = " << k << " suma = " << sumamale[it][k] << " sum2 = " << sumaduze[it][k] << '\n';
					sumaduzych += sumaduze[it][k];
					it += ((1 << k));
				}
				k--;
			}

            // cout << "it = " << it << '\n';
            // cout << sumamalych << " " << sumaduzych << '\n';
            // cout << przedwlewo << " " << zaprawo << '\n';
            // cout << gdziel[1] << '\n';
            // cout.flush();

			
			if (l < it) {
				lew = max(lew, gdziel[sumamalych + przedwlewo] + 1);
				praw = min(praw, gdziep[sumaduzych + zaprawo] - 1);
			}
			liczbawlewo = ilewlewo[praw];
			if (lew - 1 >= 0) {
				liczbawlewo -= ilewlewo[lew - 1];
			}
			liczbawprawo = ilewprawo[praw];
			if (lew - 1 >= 0) {
				liczbawprawo -= ilewprawo[lew - 1];
			}
			przedwlewo = 0;
			if (lew > 0) {
				przedwlewo = ilewlewo[lew - 1];
			}
			zaprawo = ilewprawo[n - 1];
			if (praw >= 0) {
				zaprawo -= ilewprawo[praw];
			}
            // cout << "lew = " << lew << " praw = " << praw << " it = " << it << " x = " << T[it] << '\n';
            if (it <= r) {
                ll x = T[it];
				if (x <= lew) {
					if (x <= liczbawlewo) {
						lew = max(lew, gdziel[x + przedwlewo] + 1);
					}
					else {
						jakiet = lew + liczbawprawo;
						if (x <= jakiet) {
							jakiet = (jakiet + x) % (n + 1);
						}
						else {
							jakiet = (jakiet + x + 1) % (n + 1);
						}
						lew = jakiet;
						praw = jakiet - 1;
					}
				}
				else if (x <= praw + 1) {
                    x--;
                    ll odbl = 0;
                    ll odbr = 0;
                    odbr += ilewlewo[praw];
                    odbr -= ilewlewo[x];
                    odbl = ilewprawo[x - 1];
                    // cout << odbl << " " << odbr << '\n';
                    ll poprawo = 0;
                    poprawo += ilewprawo[n - 1];
                    if (x - 1 >= 0) {
                        poprawo -= ilewprawo[x - 1];
                    }
                    if (lew - 1 >= 0) {
                        odbl -= ilewprawo[lew - 1];
                    }
                    if (odbl < odbr) {
                        ll now = gdziel[odbl + 1 + ilewlewo[x]] + 1;
                        x = lew;
                        lew = now;
                        liczbawlewo = ilewlewo[praw];
                        if (lew - 1 >= 0) {
                            liczbawlewo -= ilewlewo[lew - 1];
                        }
                        liczbawprawo = ilewprawo[praw];
                        if (lew - 1 >= 0) {
                            liczbawprawo -= ilewprawo[lew - 1];
                        }
                        przedwlewo = 0;
                        if (lew > 0) {
                            przedwlewo = ilewlewo[lew - 1];
                        }
                        zaprawo = ilewprawo[n - 1];
                        if (praw >= 0) {
                            zaprawo -= ilewprawo[praw];
                        }
                        if (x <= liczbawlewo) {
                            lew = max(lew, gdziel[x + przedwlewo] + 1);
                        }
                        else {
                            jakiet = lew + liczbawprawo;
                            if (x <= jakiet) {
                                jakiet = (jakiet + x) % (n + 1);
                            }
                            else {
                                jakiet = (jakiet + x + 1) % (n + 1);
                            }
                            lew = jakiet;
                            praw = jakiet - 1;
                        }
                    }
                    else {
                        ll now = gdziep[odbr + poprawo] - 1;
                        x = praw + 1;
                        praw = now;
                        liczbawlewo = ilewlewo[praw];
                        if (lew - 1 >= 0) {
                            liczbawlewo -= ilewlewo[lew - 1];
                        }
                        liczbawprawo = ilewprawo[praw];
                        if (lew - 1 >= 0) {
                            liczbawprawo -= ilewprawo[lew - 1];
                        }
                        przedwlewo = 0;
                        if (lew > 0) {
                            przedwlewo = ilewlewo[lew - 1];
                        }
                        zaprawo = ilewprawo[n - 1];
                        if (praw >= 0) {
                            zaprawo -= ilewprawo[praw];
                        }
                        if (n - x <= liczbawprawo) {
                            praw = min(praw, gdziep[n - x + zaprawo] - 1);
                        }
                        else {
                            jakiet = lew + liczbawprawo;
                            if (x <= jakiet) {
                                jakiet = (jakiet + x) % (n + 1);
                            }
                            else {
                                jakiet = (jakiet + x + 1) % (n + 1);
                            }
                            lew = jakiet;
                            praw = jakiet - 1;
                        }
                    }
				}
				else  {
					if (n - x <= liczbawprawo) {
						praw = min(praw, gdziep[n - x + zaprawo] - 1);
					}
                    else {
                        jakiet = lew + liczbawprawo;
                        if (x <= jakiet) {
                            jakiet = (jakiet + x) % (n + 1);
                        }
                        else {
                            jakiet = (jakiet + x + 1) % (n + 1);
                        }
                        lew = jakiet;
                        praw = jakiet - 1;
                    }
				}
            }
			l = it + 1;
			if (l > r) {
				czykonc = true;
				break;
			}
		}
        // cout << "lew = " << lew << " praw = " << praw << '\n';
        // cout << "l = " << l << " r = " << r << '\n';
        // cout.flush();
        if (czykonc) {
            ll liczbawlewo = ilewlewo[praw];
			if (lew - 1 >= 0) {
				liczbawlewo -= ilewlewo[lew - 1];
			}
			ll liczbawprawo = ilewprawo[praw];
			if (lew - 1 >= 0) {
				liczbawprawo -= ilewprawo[lew - 1];
			}
            cout << lew + liczbawprawo << '\n';
            continue;
        }
		l += MAXN;
		r += MAXN;
		deque<ll> dq;
		deque<ll> dq2;
		ll gdzie = lew;
		while (l < r) {
			if (l % 2 == 1) {
				dq.push_back(l);
				l++;
			}
			if (r % 2 == 0) {
				dq2.push_front(r);
				r--;
			}
			l /= 2;
			r /= 2;
		}
		if (l == r) {
			dq.push_back(l);
		}
		queue<ll> q;
		while (!dq.empty()) {
			q.push(dq.front());
			dq.pop_front();
		}
		while (!dq2.empty()) {
			q.push({dq2.front()});;
			dq2.pop_front();
		}
		while (!q.empty()) {
			ll v = q.front();
			q.pop();
			ll sz = seg[v].size();
			// cout << "sz = " << sz << '\n';
			ll poc = 0;
			ll kon = sz;
			ll odp = sz;
			while (poc < kon) {
				ll sr = (poc + kon)/2;
				if (seg[v][sr].l > gdzie) {
					kon = sr;
				}
				else {
					poc = sr + 1;
					odp = sr;
				}
			}
			// cout << "gdzie = " << gdzie << '\n';
			// cout << "odp = " << odp << '\n';
			gdzie += seg[v][odp].a;
			gdzie %= (n + 1);
		}
		cout << gdzie << '\n';
	}
	return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 12 / 12
• Subtask 3: 10 / 10
• Subtask 4: 11 / 11
• Subtask 5: 26 / 26
• Subtask 6: 17 / 17
• Subtask 7: 21 / 21