QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#484886#6509. Not Another Range Query ProblemBalintRWA 16ms13184kbC++204.3kb2024-07-20 04:37:472024-07-20 04:37:48

Judging History

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

  • [2024-07-20 04:37:48]
  • 评测
  • 测评结果:WA
  • 用时:16ms
  • 内存:13184kb
  • [2024-07-20 04:37:47]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef complex<double> cpx;
template <typename T> using minPq = priority_queue<T, vector<T>, greater<T>>;
#define ms(a, x) memset(a, x, sizeof(a))
#define pb push_back
#define fs first
#define sn second
#define ALL(v) begin(v), end(v)
#define SZ(v) ((int) (v).size())
#define lbv(v, x) (lower_bound(ALL(v), x) - (v).begin())
#define ubv(v, x) (upper_bound(ALL(v), x) - (v).begin())
template <typename T> inline void UNIQUE(vector<T> &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
#define FR(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define dbg(x) {cerr << #x << ' ' << x << endl;}
#define dbgArr(arr, n) {cerr << #arr; FR(_i, n) cerr << ' ' << (arr)[_i]; cerr << endl;}
template <typename T, typename U>
ostream& operator<<(ostream &os, pair<T, U> p){return os << "(" << p.fs << ", " << p.sn << ")";}

struct Blk {
    bool col;
    int *l, *r;

    int size(){
        return r-l;
    }
};

const int TSZ = 1 << 19;
const int MN = 5e5 + 5;

namespace Tree {
    int tree[TSZ*2];

    void upd(int l, int r, int v){
        for(l += TSZ, r += TSZ; l < r; l >>= 1, r >>= 1){
            if(l & 1) tree[l++] += v;
            if(r & 1) tree[--r] += v;
        }
    }

    int query(int i){
        int res = 0;
        for(i += TSZ; i; i >>= 1) res += tree[i];
        return res;
    }

    int bsearch(int l, int r, int v){
        int lo = l, hi = r;
        while(lo < hi){
            int mid = (lo+hi)/2;
            if(query(mid) < v) lo = mid+1;
            else hi = mid;
        }
        return lo;
    }
}

void merge(Blk &a, Blk &b){
    // dbgArr(a.l, SZ(a));
    // dbgArr(b.l, SZ(b));
    Tree::upd(*b.l, *(&b)[1].l, SZ(a));
    if(SZ(a) >= SZ(b)) copy(b.l, b.r, a.r), a.r += SZ(b);
    else copy_backward(a.l, a.r, b.l -= SZ(a)), a = move(b);
    // dbgArr(a.l, SZ(a));
}

int n, q;
string str;
int mem[MN];
Blk blks[MN];
int nb, pref[MN];
int ans[MN];
vector<pair<pii, int>> qrys[MN];

void proc(int t){
    FR(i, nb) pref[i+1] = pref[i] + SZ(blks[i]);
    // FR(i, nb) dbgArr(blks[i].l, SZ(blks[i]));
    // cerr << endl;
    FR(i, nb) assert(SZ(blks[i]));

    for(auto [pr, ind] : qrys[t]){
        auto [l, r] = pr;
        int li = upper_bound(blks, blks+nb, l, [](const int &a, const Blk &b){
            return a < *b.l;
        }) - blks - 1;
        int ri = upper_bound(blks, blks+nb, r, [](const int &a, const Blk &b){
            return a < *b.l;
        }) - blks - 1;

        if(ri < 0) continue;
        li = max(0, li);

        int lp = lower_bound(blks[li].l, blks[li].r, l) - blks[li].l;
        int rp = Tree::query(r)+1;

        // dbg(li);
        // dbg(ri);
        // dbg(lp);
        // dbg(rp);
        // dbgArr(blks[li].l, SZ(blks[li]));
        // dbgArr(blks[ri].l, SZ(blks[ri]));

        if(li == ri) ans[ind] = max(0, rp-lp);
        else ans[ind] = SZ(blks[li]) - lp + pref[ri] - pref[li+1] + rp;
    }

    Tree::upd(0, TSZ, -1);
    int oldNb = nb;
    nb = 0;
    FR(i, oldNb){
        int lv = *blks[i].l, rv = *blks[i+1].l;
        Tree::upd(lv, Tree::bsearch(lv, rv, -1), 1);
        blks[i].r--;
        if(!SZ(blks[i])){
            if(nb) Tree::upd(lv, rv, SZ(blks[nb-1]));
            continue;
        }
        if(nb && blks[i].col == blks[nb-1].col) merge(blks[nb-1], blks[i]);
        else blks[nb++] = move(blks[i]);
    }
    blks[nb].l = mem+n;
}

int main(){
    cin.sync_with_stdio(0); cin.tie(0);
    cin >> n >> q >> str;
    FR(i, q){
        int l, r, t;
        cin >> l >> r >> t;
        l--; r--;
        qrys[t].pb({{l, r}, i});
    }

    FR(i, n+1) mem[i] = i;

    FR(i, n){
        if(!i || str[i] != str[i-1]) blks[nb].l = blks[nb].r = mem+i, blks[nb++].col = str[i]-'0';
        Tree::upd(i, i+1, SZ(blks[nb-1]));
        blks[nb-1].r++;
    }
    blks[nb].l = mem+n;

    FR(t, n+1) proc(t);

    FR(i, q) cout << ans[i] << '\n';
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 11840kb

input:

9 7
100110001
2 5 1
3 6 1
4 8 2
2 7 1
1 9 1
1 9 0
1 9 8

output:

2
1
1
3
4
9
0

result:

ok 7 numbers

Test #2:

score: -100
Wrong Answer
time: 16ms
memory: 13184kb

input:

100 100000
0000011010101000111011110110000111110101101010111111101011011010111001111010111000001000011000001010
76 99 3
25 84 7
45 83 11
10 12 10
69 86 4
27 28 1
22 42 42
4 86 25
26 91 22
20 81 17
50 78 0
77 93 50
31 50 34
7 46 13
78 89 0
79 98 0
2 84 33
58 93 11
56 75 2
55 77 68
7 9 41
44 46 11
47 ...

output:

8
16
6
0
3
0
0
0
1
6
29
0
0
0
12
20
0
0
5
0
0
0
0
0
0
0
0
11
18
1
0
57
0
0
11
0
3
0
0
3
0
0
0
0
0
0
0
0
3
0
0
3
0
0
19
0
0
0
16
10
0
0
3
0
3
0
1
10
12
0
0
0
6
0
5
5
0
16
0
19
29
40
21
14
26
0
21
3
0
10
18
0
5
0
5
6
0
0
5
0
0
1
51
0
0
0
22
11
0
21
5
9
15
0
13
22
2
23
0
26
0
0
0
0
0
0
11
46
59
2
9
43
...

result:

wrong answer 2nd numbers differ - expected: '13', found: '16'