Submission #1183542

#TimeUsernameProblemLanguageResultExecution timeMemory
1183542niepamietamhaslaModern Machine (JOI23_ho_t5)C++20
0 / 100
51 ms19132 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; int n, m; struct c{ int a; int b; int dod; }; struct d{ vector<c> swapy; }; vector<int> krasnoludki; const int base = 1 << 17; d drzew[2 * base]; int M; bool comp(const c &c1, const c &c2){ if(c1.a != c2.a){ return c1.a < c2.a; } else{ cout << "HUHH\n"; exit(0); } return false; } int oblicz(int w, int a, int b, int akt_a, int akt_b, int curr){ if(a <= akt_a and akt_b <= b){ int p = 0; int k = drzew[w].swapy.size() - 1; while(p != k){ int sr = (p + k) / 2; if(drzew[w].swapy[sr].b < curr){ p = sr + 1; } else{ k = sr; } } return (curr + drzew[w].swapy[p].dod) % M; } if(akt_a > b or akt_b < a) return curr; int mid = (akt_a + akt_b) / 2; curr = oblicz(2 * w, a, b, akt_a, mid, curr); curr = oblicz(2 * w + 1, a, b, mid + 1, akt_b, curr); return curr; } int main(){ // ios_base::sync_with_stdio(0); // cin.tie(0); // cout.tie(0); cin >> n >> m; M = n + 1; int a, b; int ile = 0; int czy = false; string s; cin >> s; for(int i = 0; i < n; ++i){ if(s[i] == '>' or s[i] == 'R'){ if(czy) exit(0); ile++; } else{ czy = true; } } for(int i = 0; i < m; ++i){ cin >> a; krasnoludki.push_back(a); drzew[i + base].swapy = {{0, a - 1, a + 1}, {a, n, a}}; } for(int i = m + base; i < 2 * base; ++i){ drzew[i].swapy = {{0, n, 0}}; } for(int i = base - 1; i > 0; --i){ //cout << i << " i\n"; auto v1 = drzew[2 * i].swapy; auto v2 = drzew[2 * i + 1].swapy; vector<c> odp; // for(auto u : v1){ // cout << u.a << " " << u.b << " " << u.dod << " syn1\n"; // } // for(auto u : v2){ // cout << u.a << " " << u.b << " " << u.dod << " syn2\n"; // } 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); } } odp = tmp; // for(auto u : odp){ // cout << u.a << " " << u.b << " " << u.dod << " po zlozeniu\n"; // } sort(odp.begin(),odp.end(),comp); drzew[i].swapy = odp; } //cout << ile << " ile\n"; int q; cin >> q; for(int i = 0; i < q; ++i){ cin >> a >> b; cout << oblicz(1, a, b, 1, base, ile) << "\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...