| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 579369 | josanneo22 | Street Lamps (APIO19_street_lamps) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<stdlib.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pair<int, int> > vpii;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b); i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
#define mp make_pair
#define pb push_back
#define rsz resize
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define f first
#define s second
#define out(x) cout<<x<<'\n';
#define in(x) cin>>x;
#define inarr(a,x,y) for(int i=x;i<y;i++){cin>>a[i];}
#define incor(a,x,y) for(int i=x;i<y;i++){cin>>a[i].f>>a[i].s;}
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
const int mod = 1e9 + 7;void normal()
{
ios_base::sync_with_stdio(0); cin.tie(0);
}
char change(char x)
{
if(x=='0') return '1';
return '0';
}
int n, q;
vll v, t;
void build(int tl, int tr, int ind)
{
if (tl == tr)
{
t[ind] = v[tl];
return;
}
int mid = (tl + tr) / 2;
build(tl, mid, 2 * ind);
build(mid + 1, tr, 2 * ind + 1);
t[ind] = max(t[2 * ind] ,t[2 * ind + 1]);
return;
}
ll query(int tl, int tr, int ql, int qr, int ind)
{
if (tl >= ql and tr <= qr)
return t[ind];
if (tr < ql || tl > qr)
return -1LL;
int mid = (tl + tr) / 2;
ll left = query(tl, mid, ql, qr, 2 * ind);
ll right = query(mid + 1, tr, ql, qr, 2 * ind + 1);
return max(left, right);
}
void update(int tl, int tr, int p, int diff, int ind)
{
if (p < tl || p > tr)
return;
if (tl == tr)
{
t[ind] = diff;
return;
}
int mid = (tl + tr) / 2;
update(tl, mid, p, diff, 2 * ind);
update(mid + 1, tr, p, diff, 2 * ind + 1);
t[ind] = max(t[2 * ind] , t[2 * ind + 1]);
return;
}
void solve()
{
cin>>n>>q;
if(n<=100 && q<=100)
{
vpii queries(q);
string ori;cin>>ori;
FOR(i,0,q)
{
string x; cin>>x;
if(x=="query")
{
int a,b;
cin>>a>>b;
a--;b--;
queries[i]={a,b};
int ans=0;
string str=ori;
FOR(j,0,i+1)
{
int cnt=0;
FOR(k,a,b)
{
if(str[k]=='1')
cnt++;
}
if(cnt==(b-a))
ans++;
if(queries[j].s==-1) str[queries[j].f]=change(str[queries[j].f]);
}
out(ans);
}
else
{
int a;
cin>>a;
a--;
queries[i]={a,-1};
}
}
}
/*string ori; cin>>ori;
vpii t;
FOR(i,0,n)
{
t.pb(mp(0,0));//cur_dist| last_switch
}
FOR(i,1,q+1)
{
string type; cin>>type;
if(type=="query")
{
int a,b; cin>>a>>b;
if(ori[a]==1)
{
cout<<t[a].f+i-t[a].s<<'\n';
}
else
cout<<t[a].f<<'\n';
}
else
{
int a; cin>>a;
if(ori[a]=='1')
{
t[a].f+=i-t[a].s-1;
}
t[a].s=i;
if(ori[a]=='1') ori[a]='0';
else ori[a]='1';
}
}*/
string ori;
cin>>ori;
v.rsz(n);
FOR(i,0,n)
{
if(ori[i]=='0') v[i]=INT_MAX;
else v[i]==0LL;
}
t.resize(4 * n + 2);
build(0, n - 1, 1);
FOR(i,1,q+1)
{
string type; cin>>type;
if(type=="query")
{
int a,b; cin>>a>>b;
ll x=query(0,n-1,a-1,b-1,1);
if(x==INT_MAX) cout<<"0\n";
else cout<<i-x<<endl;
}
else
{
int a; cin>>a;
if(ori[a]=='0')
{
update(0,n-1,a-1,i,1);
}
}
}
return;
}
int main()
{
normal("");
int t=1;
while(t--)
{
solve();
}
return 0;
}