이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)
using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;
//Note to self: Check for overflow
void solvebrute(int n, string &s, int q, vector<pii> &qrys)
{
vector<string> verzije;
verzije.pb(s);
for (auto it : qrys)
{
if (it.xx>-1)
{
int kolko=0;
for (auto s : verzije)
{
bool moze=true;
ff(i,it.xx-1,it.yy-1) if (s[i]=='0') moze=false;
if (moze) kolko++;
}
cout<<kolko<<"\n";
}
verzije.pb(verzije.back());
if (it.xx==-1) verzije.back()[it.yy-1]='0'+'1'-verzije.back()[it.yy-1];
}
}
void solvepoints(int n, string &s, int q, vector<pii> &qrys)
{
}
const int N=6'000'005;
int val[N],L[N],R[N];
int idx=0;
void add(int p, int q, int l, int r, int s, int x)
{
val[p]=val[q]+x;
if (l==r) return;
int mid=(l+r)/2;
if (s<=mid) L[p]=++idx,R[p]=R[q],add(L[p],L[q],l,mid,s,x);
else L[p]=L[q],R[p]=++idx,add(R[p],R[q],mid+1,r,s,x);
}
int sum(int p, int l, int r, int ll, int rr)
{
if (!p || ll>r || rr<l) return 0;
if (ll<=l && rr>=r) return val[p];
int mid=(l+r)/2;
return sum(L[p],l,mid,ll,rr)+sum(R[p],mid+1,r,ll,rr);
}
int root[300005];
void solvepersistent(int n, string &s, int q, vector<pii> &qrys)
{
++idx; //obezbedimo root - 1
int temp;
ff(i,0,n) if (s[i]=='1') temp=++idx,add(temp,root[0],0,n-1,i,1),root[0]=temp;
ff(i,0,q)
{
root[i+1]=root[i];
int a=qrys[i].xx,b=qrys[i].yy;
if (a==-1) root[i+1]=++idx,add(root[i+1],root[i],0,n-1,b-1,s[b-1]=='1'?-1:1),s[b-1]='0'+'1'-s[b-1];
else
{
int l=-1,r=i+1;
while (r-l>1)
{
int mid=(l+r)/2;
if (sum(root[mid],0,n-1,a-1,b-2)<b-a) l=mid;
else r=mid;
}
cout<<(i+1)-r<<"\n";
}
}
}
int main()
{
FAST;
int n,q; cin>>n>>q;
string s; cin>>s;
vector<bool> pomcina(n+3,0);
bool susedni=true;
bool imaoff=false;
vector<pii> qrys; //a,b znaci a,b; -1,i znaci toggle i
while (q--)
{
string tip; cin>>tip;
if (tip=="toggle")
{
int i; cin>>i;
qrys.pb({-1,i});
if (s[i-1]=='1' || pomcina[i-1]) imaoff=true;
pomcina[i-1]=true;
}
else
{
int a,b; cin>>a>>b;
qrys.pb({a,b});
if (b-a>1) susedni=false;
}
}
if (n<=100 && q<=100) solvebrute(n,s,(int)qrys.size(),qrys);
else if (!imaoff) solvepersistent(n,s,(int)qrys.size(),qrys);
else if (susedni) solvepoints(n,s,(int)qrys.size(),qrys);
}
//Note to self: Check for overflow
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |