oj.uz

Submission #949557

# Submission time Handle Problem Language Result Execution time Memory
949557 2024-03-19T10:48:10 Z peterandvoi Modern Machine (JOI23_ho_t5) C++17
37 / 100
 693 ms 86856 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, r, L, R;

    from_to(): l(0), r(0), L(0), R(0) {};

    from_to(int l, int r, int L, int R): l(l), r(r), L(L), R(R) {};

    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, br, al, ar] : a) {
        int L = lower_bound(b.begin(), b.end(), from_to(al + 1, 0, 0, 0)) - b.begin() - 1;
        int R = lower_bound(b.begin(), b.end(), from_to(ar + 1, 0, 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, bl + len - 1, tl, add(tl, len - 1));
            bl += len;
            al = add(al, len);
        }
    }
    return res;
}

void bld(int id, int l, int r) {
    if (l == r) {
        tree[id].emplace_back(0, a[l] - 1, add(0, a[l] + 1), add(a[l] - 1, a[l] + 1));
        tree[id].emplace_back(a[l], n, add(a[l], a[l]), add(n, a[l]));
    } 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, 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:64:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In function 'int qry(int, int, int, int, int, int)':
Main.cpp:80:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |     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 3 ms 11608 KB Output is correct
2 Correct 198 ms 35760 KB Output is correct
3 Correct 210 ms 36172 KB Output is correct
4 Correct 106 ms 25412 KB Output is correct
5 Correct 101 ms 35668 KB Output is correct
6 Correct 108 ms 36284 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11608 KB Output is correct
2 Correct 198 ms 35760 KB Output is correct
3 Correct 210 ms 36172 KB Output is correct
4 Correct 106 ms 25412 KB Output is correct
5 Correct 101 ms 35668 KB Output is correct
6 Correct 108 ms 36284 KB Output is correct
7 Correct 3 ms 11612 KB Output is correct
8 Correct 3 ms 11612 KB Output is correct
9 Correct 3 ms 11612 KB Output is correct
10 Correct 6 ms 12556 KB Output is correct
11 Correct 609 ms 86856 KB Output is correct
12 Correct 693 ms 86824 KB Output is correct
13 Correct 304 ms 86476 KB Output is correct
14 Correct 378 ms 86780 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11608 KB Output is correct
2 Correct 198 ms 35760 KB Output is correct
3 Correct 210 ms 36172 KB Output is correct
4 Correct 106 ms 25412 KB Output is correct
5 Correct 101 ms 35668 KB Output is correct
6 Correct 108 ms 36284 KB Output is correct
7 Incorrect 2 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 -