QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #108176 | #6509. Not Another Range Query Problem | vme50 | TL | 1ms | 26184kb | C++17 | 1.7kb | 2023-05-23 19:43:40 | 2023-05-23 19:43:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define N 500005
#define pb push_back
int n,m,st[N],tmp[N],ans[N],rt[N];char a[N];
struct List {int pr,sf;}ls[N];
struct Query {int l,r,id;};vector<Query> vc[N];
struct BitArray
{
int bt[N];void build() {for(int i=1;i<=n;++i) bt[i]=i&-i;}
void upd(int x,int vl) {for(;x<=n;x+=x&-x) bt[x]+=vl;}
int qSm(int x) {int res=0;for(;x;x-=x&-x) res+=bt[x];return res;}
int qry(int x)
{
int res=0;
for(int i=18;i>=0;--i) if(res+(1<<i)<=n && bt[res+(1<<i)]<x)
res+=1<<i;return res+1;
}
}BIT1,BIT2;
int findRt(int u) {return u==rt[u]?u:rt[u]=findRt(rt[u]);}
void merge(int u,int v) {u=findRt(u);v=findRt(v);if(u!=v) rt[u]=v,BIT2.upd(u,-1);}
int main()
{
scanf("%d %d %s",&n,&m,a+1);iota(rt+1,rt+n+1,1);
for(int i=1,l,r,x;i<=m;++i)
{scanf("%d %d %d",&l,&r,&x);if(x) vc[x].pb((Query) {l,r,i});else ans[i]=r-l+1;}
for(int i=0;i<=n;++i) ls[i].sf=i+1,ls[i+1].pr=i;
for(int i=1;i<=n;++i) if(a[i]!=a[i-1]) st[++st[0]]=i;BIT1.build();BIT2.build();
for(int i=1,t,t1;i<=n;++i)
{
if(!st[0]) break;t=tmp[0]=0;
for(int j=1;j<=st[0]+1;++j)
if(j==1 || j>st[0] || ls[st[j]].pr!=st[j-1])
{
if(j>1 && ls[st[j-1]].sf<=n && a[t]!=a[ls[st[j-1]].sf])
tmp[++tmp[0]]=ls[st[j-1]].sf;t=ls[st[j]].pr;
if(j>1) t1=BIT1.qSm(st[j]),merge(BIT2.qry(t1),BIT2.qry(t1-1));
}else t1=BIT1.qSm(st[j]),merge(BIT2.qry(t1),BIT2.qry(t1-1));
for(int j=1;j<=st[0];++j)
{
ls[ls[st[j]].pr].sf=ls[st[j]].sf;
ls[ls[st[j]].sf].pr=ls[st[j]].pr;BIT1.upd(st[j],-1);
}copy(tmp,tmp+tmp[0]+1,st);
for(auto [l,r,id]:vc[i]) ans[id]=max(BIT1.qSm(r)-BIT2.qSm(findRt(l))+1,0);
}for(int i=1;i<=m;++i) printf("%d\n",ans[i]);return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 26184kb
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
Time Limit Exceeded
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 ...