Submission #1179627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179627		patgra	Modern Machine (JOI23_ho_t5)	C++20	100 / 100	1059 ms	79820 KiB

Main

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto a : (b))
#define repIn2(a, b, c) for(auto [a, b] : (c))
#define repInAmp2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

constexpr int maxn = 12e4 + 7, maxTreeBase = 1 << 17, maxLog = 16, inf = 1e9 + 7;
int n, m;
bool ogRight[maxn], myRight[maxn];
int arr[maxn], prefSum[maxn];
vector<pair<pair<int, int>, int>> t[2 * maxTreeBase];
int treeBase;
int maxH1[maxn][maxLog], minH2[maxn][maxLog];
ll prefSumH1[maxn], prefSumH2[maxn];

constexpr int bufSize = 5* (60 + maxn * 2 + maxn * 10 + maxn * 2 * 10);
char buffer[bufSize];
int bufI;
void initBuffer() {
    fread_unlocked(buffer, sizeof(char), bufSize, stdin);
}
void getInt(int& x) {
    while(buffer[bufI] > '9' || buffer[bufI] < '0') bufI++;
    x = 0;
    while(buffer[bufI] <= '9' && buffer[bufI] >= '0') x = 10 * x + buffer[bufI] - '0', bufI++;
}

inline int getMaxH1(int l, int r) {
    if(l == r) return maxH1[l][0];
    int k = 31 - __builtin_clz(r - l + 1);
    return max(maxH1[l][k], maxH1[r - (1 << k) + 1][k]);
}
inline int getMinH2(int l, int r) {
    if(l == r) return minH2[l][0];
    int k = 31 - __builtin_clz(r - l + 1);
    return min(minH2[l][k], minH2[r - (1 << k) + 1][k]);
}

inline int truePrefSum(int l, int r, int x) {
    if(x <= l) return x;
    if(x >= r) return l + 1 + prefSum[r] - prefSum[l + 1];
    return l + 1 + prefSum[x] - prefSum[l + 1];
}
inline int cntRight(int l, int r, int il, int ir) {
    return truePrefSum(l, r, ir + 1) - truePrefSum(l, r, il);
}
inline int cntLeft(int l, int r, int il, int ir) {
    return (ir - il + 1) - cntRight(l, r, il, ir);
}

pair<int, int> f(int l, int r, int a) {
    DC << "f({" << l << ' ' << r << "}, " << a << "): " << eol << " ";
    int bl = cntRight(l, r, 0, a - 1);
    int br = cntLeft(l, r, a + 1, n - 1);
    DC << " bl = " << bl << "; br = " << br << eol;
    if(bl >= br) {
        // wylatujemy z prawej
        // pierwsze br wsrod bl przechodzi na br
        // szukamy ostatniego miejsca gdzie cntRight(0, a - 1) + br < bl
        DC << " przekabacamy " << br << " typow z lewej " << eol;
        int p = 0, s, k = a;

        bool xd = false;
        rep(xdd, 1, 2) if(p < a - xdd && cntRight(l, r, 0, a - 1 - xdd) + br < bl) { p = a - xdd; xd = true; break; }

        while(k - p > 1) {
            s = (p + k) / 2;
            if(cntRight(l, r, 0, s - 1) + br < bl) p = s;
            else k = s;
        }
        if(bl > br) p++;
        return {min(l, p - 1), p};
    }
    else {
        // wylatujemy z lewej
        // pierwsze bl + 1 wsrod br przechodzi na bl
        // szukamy pierwszego miejsca gdzie cntLeft(a + 1, n - 1) + bl + 1 <= br
        DC << " przekabacamy " << bl + 1 << " typow z prawej " << eol;
        int p = a, s, k = n - 1;

        bool xd = false;
        rep(xdd, 1, 2) if(k > a + xdd && cntLeft(l, r, a + 1 + xdd, n - 1) + bl + 1 <= br) { k = a + xdd; xd = true; break; }

        while(k - p > 1) {
            s = (p + k) / 2;
            if(cntLeft(l, r, s + 1, n - 1) + bl + 1 <= br) k = s;
            else p = s;
        }
        return {k, max(k + 1, r)};
    }
    return {0, 0};
}

void calcTree() {
    DC << "Builbimg tree" << eol;
    treeBase = 1 << (32 - __builtin_clz(m));
    rep(i, 0, m) t[i + treeBase] = { {{0, arr[i] - 1}, arr[i] + 1}, {{arr[i], n}, arr[i]}};
    rep(i, m, treeBase) t[i + treeBase] = { {{0, n}, 0} };
    repD(i, treeBase - 1, 0) {
        vector<pair<pair<int, int>, int>> treatSeparately;
        repIn2(lr, add, t[i * 2]) {
            auto [l, r] = lr;
            auto nl = (l + add) % (n + 1), nr = (r + add) % (n + 1);
            if(nl > nr) { treatSeparately.pb({{l, ((n - add) % (n + 1) + n + 1) % (n + 1)}, add}); treatSeparately.pb({{((-add) % (n + 1) + n + 1) % (n + 1), r}, add}); continue; }
            auto it = ranges::upper_bound(t[2 * i + 1], make_pair(make_pair(nr, (int)1e9), (int)1e9));
            if(it == t[2 * i + 1].begin()) it = t[2 * i + 1].end();
            auto start = it;
            do {
                it--;
                auto [l2, r2] = it -> first;
                if(r2 < nl || nr < l2) break;
                t[i].pb(make_pair(make_pair(((max(l2, nl) - add) % (n + 1) + n + 1) % (n + 1), ((min(nr, r2) - add) % (n + 1) + n + 1) % (n + 1)), (add + it -> second) % (n + 1)));
                if(it == t[2 * i + 1].begin()) it = t[2 * i + 1].end();
            } while(it != start);
        }
        repIn2(lr, add, treatSeparately) {
            auto [l, r] = lr;
            auto nl = (l + add) % (n + 1), nr = (r + add) % (n + 1);
            if(nl > nr) { treatSeparately.pb({{l, ((n - add) % (n + 1) + n + 1) % (n + 1)}, add}); treatSeparately.pb({{((-add) % (n + 1) + n + 1) % (n + 1), r}, add}); continue; }
            auto it = ranges::upper_bound(t[2 * i + 1], make_pair(make_pair(nr, (int)1e9), (int)1e9));
            if(it == t[2 * i + 1].begin()) it = t[2 * i + 1].end();
            auto start = it;
            do {
                it--;
                auto [l2, r2] = it -> first;
                if(r2 < nl || nr < l2) break;
                t[i].pb(make_pair(make_pair(((max(l2, nl) - add) % (n + 1) + n + 1) % (n + 1), ((min(nr, r2) - add) % (n + 1) + n + 1) % (n + 1)), (add + it -> second) % (n + 1)));
                if(it == t[2 * i + 1].begin()) it = t[2 * i + 1].end();
            } while(it != start);
        }
        ranges::stable_sort(t[i]);
    }
    DEBUG {
        DC << "Tree built        /\\" << eol << eol;
    }
}

vector<int> basesL, basesR;
int queryTree(int l, int r, int startState) {
    DC << "Q " << l << ' ' << r << "  startState " << startState << eol;
    l += treeBase;
    r += treeBase;
    basesL.clear(); basesR.clear();
    basesL.pb(l);
    if(l != r) basesR.pb(r);
    while(l / 2 != r / 2) {
        if(l % 2 == 0) basesL.pb(l + 1);
        if(r % 2 == 1) basesR.pb(r - 1);
        l /= 2;
        r /= 2;
    }
    repIn(i, basesL) {
        auto it = ranges::upper_bound(t[i], make_pair(make_pair(startState, (int)1e9), (int)1e9));
        if(it == t[i].begin()) it = t[i].end();
        it--;
        DC << (it -> first.first) << ' ' << (it -> first.second) << "  adds " << (it -> second) << " -> (" << startState << " + " << (it -> second) << ") % " << n + 1 << " = ";
        startState = (startState + it -> second) % (n + 1);
        DC << startState << eol;
    }
    ranges::reverse(basesR);
    repIn(i, basesR) {
        auto it = ranges::upper_bound(t[i], make_pair(make_pair(startState, (int)1e9), (int)1e9));
        if(it == t[i].begin()) it = t[i].end();
        it--;
        DC << (it -> first.first) << ' ' << (it -> first.second) << "  adds " << (it -> second) << " -> (" << startState << " + " << (it -> second) << ") % " << n + 1 << " = ";
        startState = (startState + it -> second) % (n + 1);
        DC << startState << eol;
    }
    return startState;
}

int binsearch(int start, int end, int l, int r) {
    // szukamy ostatniego miejsca gdzie maxH1 <= l && minH2 >= r oraz sie nie spotkaja
    int p = start - 1, s, k = end;
    while(k - p > 1) {
        s = (p + k) / 2;
        ll sumH1 = prefSumH1[s + 1] - prefSumH1[start];
        ll sumH2 = prefSumH2[s + 1] - prefSumH2[start];
        if(getMaxH1(start, s) > l || getMinH2(start, s) < r || l + sumH1 >= r - sumH2 || cntLeft(l, r, l + 1, (l + r) / 2) < sumH1 || cntRight(l, r, (l + r) / 2 + 1, r) < sumH2) k = s;
        else p = s;
    }
    return p;
}

int main() {
    initBuffer();
    getInt(n); getInt(m);
    char c;
    while((buffer[bufI] != 'R' && buffer[bufI] != 'B') && (buffer[bufI] != '>' && buffer[bufI] != '<')) bufI++;
    rep(i, 0, n) c = buffer[bufI++], ogRight[i] = (c == 'R') || (c == '>');
    rep(i, 0, n) prefSum[i + 1] = prefSum[i] + ogRight[i];

    rep(i, 0, m) getInt(arr[i]);
    int h1Cutoff = n / 2;
    rep(i, 0, m) {
        prefSumH1[i + 1] = prefSumH1[i];
        prefSumH2[i + 1] = prefSumH2[i];
        if(arr[i] <= h1Cutoff) {
            prefSumH1[i + 1] += arr[i];
            maxH1[i][0] = arr[i] - 1;
            minH2[i][0] = inf;
        }
        else { 
            prefSumH2[i + 1] += n - arr[i];
            minH2[i][0] = arr[i] - 1;
            maxH1[i][0] = -inf;
        }
    }
    rep(k, 1, maxLog) rep(i, 0, m) maxH1[i][k] = max(maxH1[i][k - 1], maxH1[min(m - 1, i + (1 << (k - 1)))][k - 1]);
    rep(k, 1, maxLog) rep(i, 0, m) minH2[i][k] = min(minH2[i][k - 1], minH2[min(m - 1, i + (1 << (k - 1)))][k - 1]);
    calcTree();

    string output, str;

    pair<int, int> lrIni = {-1, n};
    while(lrIni.first < n && ogRight[lrIni.first + 1]) lrIni.first++;
    while(lrIni.second && !ogRight[lrIni.second - 1]) lrIni.second--;

    int q;
    getInt(q);
    rep(i, 0, q) {
        int start, end;
        getInt(start); getInt(end);
        start--; end--;
        auto [l, r] = lrIni;
        bool lastFound = false;
        while(start <= end) {
            if(l + 1 == r) {
                DC << "Spotkali sie" << eol;
                break;
            }

            int p = start - 1;
            if(!lastFound) {
                int s = start;
                ll sumH1 = prefSumH1[s + 1] - prefSumH1[start];
                ll sumH2 = prefSumH2[s + 1] - prefSumH2[start];
                if(!(getMaxH1(start, s) > l || getMinH2(start, s) < r || l + sumH1 >= r - sumH2 || cntLeft(l, r, l + 1, (l + r) / 2) < sumH1 || cntRight(l, r, (l + r) / 2 + 1, r) < sumH2)) p = binsearch(start, end, l, r);
            }
            DC << "Z lr " << l << ' ' << r << "  przedzial krasnoludkow " << start << ' ' << end << " binsearch wyplul " << p << eol;
            if(p == start - 1) {
                auto lr = f(l, r, arr[start] - 1);
                l = lr.first; r = lr.second;
                lastFound = false;
            }
            else {
                lastFound = true;
                // szukamy pierwszego miejsca gdzie cntLeft(l + 1, x) >= sumH1(start, p)
                ll sumH1 = prefSumH1[p + 1] - prefSumH1[start];
                int pp = l - 1, ss, kk = r - 1;
                while(kk - pp > 1) {
                    ss = (pp + kk) / 2;
                    if(max(0, cntLeft(l, r, l + 1, ss)) >= sumH1) kk = ss;
                    else pp = ss;
                }
                l = kk;

                // szukamy ostatniego miejsca gdzie cntRight(x, r - 1) >= sumH2(start, p)
                ll sumH2 = prefSumH2[p + 1] - prefSumH2[start];
                pp = 0, kk = r + 1;
                while(kk - pp > 1) {
                    ss = (pp + kk) / 2;
                    if(max(0, cntRight(l, r, ss, r - 1)) >= sumH2) pp = ss;
                    else kk = ss;
                }
                r = pp;

                if(l >= r) l = r - 1;

                start = p;
            }

            DC << "Nowe lr: " << l << ' ' << r << eol;
            start++;
        }
        int ans = (start <= end) ? queryTree(start, end, l + 1) : cntRight(l, r, 0, n - 1);
        str.clear();
        while(ans) str += (char)(ans % 10 + '0'), ans /= 10;
        if(str.empty()) str = '0';
        ranges::reverse(str);
        str.pb('\n');
        output += str;
    }

    fwrite_unlocked(output.c_str(), sizeof(char), output.size(), stdout);

}

Compilation message (stderr)

Main.cpp: In function 'void initBuffer()':
Main.cpp:32:19: warning: ignoring return value of 'size_t fread_unlocked(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     fread_unlocked(buffer, sizeof(char), bufSize, stdin);
      |     ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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