QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#419944#6533. Traveling in CellsXiaoretaWRE 0ms0kbC++203.0kb2024-05-24 12:57:182024-05-24 12:57:18

Judging History

你现在查看的是最新测评结果

  • [2024-05-24 12:57:18]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-05-24 12:57:18]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define sz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
#define rep(i, l, r) for (int i = l; i < r; ++i)
#define per(i, r, l) for (int i = r-1; i >= l; --i)
typedef long long ll;
typedef pair<int, int> PI;
template<typename T> bool setmax(T &a, T b) { return (a < b ? a = b, 1 : 0); }
template<typename T> bool setmin(T &a, T b) { return (a > b ? a = b, 1 : 0); }

// Set
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> Tree;

template<typename T> struct BIT {
    int n;
    vector<T> tr;
    BIT(int _n) {
        n = _n;
        tr.resize(n+1);
    }
    T prefix(int i) {
        T res = 0;
        for (; i; i -= i&(-i)) res += tr[i];
        return res;
    }
    T query(int l, int r) { return prefix(r) - prefix(l-1); }
    void modify(int i, T val) { for (; i <= n; i += i&(-i)) tr[i] += val; }
};

Tree S[300010];
void solve() {
    int n, q; cin >> n >> q;
    vector<int> c(n + 1), v(n + 1);
    BIT<ll> vbit(n);
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
        S[c[i]].insert(i);
    }
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
        vbit.modify(i, v[i]);
    }
    while (q--) {
        int t; cin >> t;
        if (t == 1 || t == 2) {
            int p, x; cin >> p >> x;
            if (t == 1) {
                S[c[p]].erase(p);
                c[p] = x;
                S[c[p]].insert(p);
            } else {
                vbit.modify(p, -v[p]);
                v[p] = x;
                vbit.modify(p, v[p]);
            }
        } else {
            int x, k; cin >> x >> k;
            vector<int> st(k);
            for (int &i : st) cin >> i;
            auto gao = [&](int f) {
                auto ck = [&](int m) {
                    int tot = 0;
                    for (int color : st) {
                        auto get = [&](int ll, int rr) {
                            return S[color].order_of_key(rr + 1) - S[color].order_of_key(ll);
                        };
                        tot += f ? get(x - m + 1, x) : get(x, x + m - 1);
                    }
                    assert(tot <= m);
                    return tot == m;
                };
                int l = 1, r = f ? x : n - x + 1;
                while (l < r) {
                    int mid = (l + r + 1) >> 1;
                    if (ck(mid)) l = mid;
                    else r = mid - 1;
                }
                return l;
            };
            int L = x - gao(1) + 1, R = x + gao(0) - 1;
            cout << vbit.query(L, R) << '\n';
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int tt; cin >> tt;
    while (tt--) solve();

    return 0;
}

詳細信息

Test #1:

score: 0
Runtime Error

input:

2
5 10
1 2 3 1 2
1 10 100 1000 10000
3 3 1 3
3 3 2 2 3
2 5 20000
2 3 200
3 3 2 1 3
3 3 3 1 2 3
1 3 4
2 1 100000
1 2 2
3 1 2 1 2
4 1
1 2 3 4
1000000 1000000 1000000 1000000
3 4 4 1 2 3 4

output:


result: