oj.uz

Submission #949555

# Submission time Handle Problem Language Result Execution time Memory
949555 2024-03-19T10:42:12 Z peterandvoi Modern Machine (JOI23_ho_t5) C++17
0 / 100
 10 ms 7640 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];

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 1 ms 3164 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3160 KB Output is correct
2 Runtime error 10 ms 7640 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3160 KB Output is correct
2 Runtime error 10 ms 7640 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3160 KB Output is correct
2 Runtime error 10 ms 7640 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #7
0 / 21.0

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