oj.uz

Submission #949771

# Submission time Handle Problem Language Result Execution time Memory
949771 2024-03-19T16:44:12 Z peterandvoi Modern Machine (JOI23_ho_t5) C++17
37 / 100
 684 ms 69420 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 120005;

int n, m, q;
char c[N];
int a[N];

struct from_to {
    int l, L, len;

    from_to(): l(0), L(0), len(0) {};

    from_to(int l, int L, int len): l(l), L(L), len(len) {};

    int r() const {
        return l + len - 1;
    }

    bool operator < (const from_to &oth) const {
        return l < oth.l;
    }
};


vector<from_to> tree[N << 2];

int add(int a, int b) {
    a += b;
    while (a >= n + 1) {
        a -= n + 1;
    }
    return a;
}

vector<from_to> cmb(const vector<from_to> &a, const vector<from_to> &b) {
    vector<from_to> res;
    for (auto [bl, al, len] : a) {
        int ar = add(al, len - 1);
        int br = add(bl, len - 1);
        int L = lower_bound(b.begin(), b.end(), from_to(al + 1, 0, 0)) - b.begin() - 1;
        int R = lower_bound(b.begin(), b.end(), from_to(ar + 1, 0, 0)) - b.begin() - 1;
        R += al > ar ? (int) b.size() : 0;
        for (int i = L; i <= R; ++i) {
            int j = i % (int) b.size();
            int delta = max(b[j].l, al) - b[j].l;
            int len = min(br - bl + 1, b[j].r() - max(b[j].l, al) + 1);
            int tl = add(b[j].L, delta);
            res.emplace_back(bl, tl, len);
            bl += len;
            al = add(al, len);
        }
    }
    return res;
}

void bld(int id, int l, int r) {
    if (l == r) {
        tree[id].emplace_back(0, add(0, a[l] + 1), a[l]);
        tree[id].emplace_back(a[l], add(a[l], a[l]), n - a[l] + 1);
    } else {
        int mid = l + r >> 1;
        bld(id << 1, l, mid);
        bld(id << 1 | 1, mid + 1, r);
        tree[id] = cmb(tree[id << 1], tree[id << 1 | 1]);
    }
}

int get(const vector<from_to> &a, int p) {
    int pos = lower_bound(a.begin(), a.end(), from_to(p + 1, 0, 0)) - a.begin() - 1;
    return add(a[pos].L, p - a[pos].l);
}

int qry(int u, int v, int p, int id = 1, int l = 1, int r = m) {
    if (u <= l && r <= v) {
        return get(tree[id], p);
    }
    int mid = l + r >> 1;
    if (u <= mid && mid < v) {
        return qry(u, v, qry(u, v, p, id << 1, l, mid), id << 1 | 1, mid + 1, r);
    }
    if (mid < u) {
        return qry(u, v, p, id << 1 | 1, mid + 1, r);
    }
    return qry(u, v, p, id << 1, l, mid);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef ngu
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
    #endif
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> c[i];
    }
    for (int i = 1; i <= m; ++i) {
        cin >> a[i];
    }
    bld(1, 1, m);
    cin >> q;
    int s = 0;
    for (int i = 1; i <= n; ++i) {
        if (c[i] != 'R') {
            break;
        }
        s = i;
    }
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << qry(l, r, s) << "\n";
    }
}

Compilation message

Main.cpp: In function 'void bld(int, int, int)':
Main.cpp:70:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In function 'int qry(int, int, int, int, int, int)':
Main.cpp:86:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 11608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 11608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 11608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11608 KB Output is correct
2 Correct 162 ms 30700 KB Output is correct
3 Correct 196 ms 30672 KB Output is correct
4 Correct 92 ms 21588 KB Output is correct
5 Correct 93 ms 30032 KB Output is correct
6 Correct 100 ms 30804 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11608 KB Output is correct
2 Correct 162 ms 30700 KB Output is correct
3 Correct 196 ms 30672 KB Output is correct
4 Correct 92 ms 21588 KB Output is correct
5 Correct 93 ms 30032 KB Output is correct
6 Correct 100 ms 30804 KB Output is correct
7 Correct 3 ms 11612 KB Output is correct
8 Correct 3 ms 11608 KB Output is correct
9 Correct 3 ms 11736 KB Output is correct
10 Correct 5 ms 12380 KB Output is correct
11 Correct 603 ms 69256 KB Output is correct
12 Correct 684 ms 69020 KB Output is correct
13 Correct 279 ms 68616 KB Output is correct
14 Correct 359 ms 69420 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11608 KB Output is correct
2 Correct 162 ms 30700 KB Output is correct
3 Correct 196 ms 30672 KB Output is correct
4 Correct 92 ms 21588 KB Output is correct
5 Correct 93 ms 30032 KB Output is correct
6 Correct 100 ms 30804 KB Output is correct
7 Incorrect 3 ms 11612 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #7
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 11608 KB Output isn't correct
2 Halted 0 ms 0 KB -