Submission #1183544

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183544		niepamietamhasla	Modern Machine (JOI23_ho_t5)	C++20	37 / 100	540 ms	65772 KiB

Main

#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);
            }
            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);
        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;
}

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