| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 121341 | WhipppedCream | 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>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
const int maxn = 3e5+5;
int st[4*maxn];
int arr[maxn];
char s[maxn];
int n;
int ask(int i, int j, int p = 1, int L = 1, int R = n)
{
if(i> R || j< L) return 0;
if(i<= L && R<= j) return st[p];
int M = (L+R)/2;
int x = ask(i, j, 2*p, L, M);
int y = ask(i, j, 2*p+1, M+1, R);
return x+y;
}
void update(int x, int dx, int p = 1, int L = 1, int R = n)
{
if(x> R || x< L) return;
if(L == R)
{
st[p] = dx;
return;
}
int M = (L+R)/2;
update(x, dx, 2*p, L, M);
update(x, dx, 2*p+1, M+1, R);
st[p] = st[2*p]+st[2*p+1];
}
int q;
int A[maxn], B[maxn];
vector<int> buck[maxn];
vector<int> tree[4*maxn];
vector<int> ms[4*maxn];
void prep(int x1, int y1, int x2, int y2)
{
buck[x1].pb(y1);
buck[x2+1].pb(y1);
buck[x1].pb(y2+1);
buck[x2+1].pb(y2+1);
}
void build(int p = 1, int L = 1, int R = n+1)
{
if(L == R)
{
tree[p] = buck[L];
sort(tree[p].begin(), tree[p].end());
tree[p].erase(unique(tree[p].begin(), tree[p].end()), tree[p].end());
// printf("[%d %d]: ", L, R);
// for(int x : tree[p]) printf("%d ", x);
// printf("\n");
ms[p].assign(tree[p].size()+2, 0);
return;
}
int M = (L+R)/2;
build(2*p, L, M);
build(2*p+1, M+1, R);
int x = 0, y = 0;
vector<int> &vL = tree[2*p];
vector<int> &vR = tree[2*p+1];
while(x< vL.size() && y< vR.size())
{
int go;
if(vL[x]< vR[y])
{
go = vL[x];
x++;
}
else
{
go = vR[y];
y++;
}
if(tree[p].empty() || go != tree[p].back()) tree[p].pb(go);
}
while(x< vL.size())
{
int go = vL[x];
x++;
if(tree[p].empty() || go != tree[p].back()) tree[p].pb(go);
}
while(y< vR.size())
{
int go = vR[y];
y++;
if(tree[p].empty() || go != tree[p].back()) tree[p].pb(go);
}
ms[p].assign(tree[p].size()+2, 0);
// printf("[%d %d]: ", L, R);
// for(int x : tree[p]) printf("%d ", x);
// printf("\n");
}
void updatems(int x, int y1, int y2, int dx, int p = 1, int L = 1, int R = n+1)
{
if(x< L || x> R) return;
int pos = lower_bound(tree[p].begin(), tree[p].end(), y)-tree[p].begin();
for(int k = pos+1; k<= tree[p].size(); k += k & (-k)) ms[p][k] += dx;
if(L == R) return;
int M = (L+R)/2;
updatems(x, y, dx, 2*p, L, M);
updatems(x, y, dx, 2*p+1, M+1, R);
}
int askms(int x1, int y1, int x2, int y2, int p = 1, int L = 1, int R = n+1)
{
if(x1> R || x2< L) return 0;
if(x1<= L && R<= x2)
{
int res = 0;
int pos = upper_bound(tree[p].begin(), tree[p].end(), y2)-tree[p].begin()-1;
for(int k = pos+1; k; k -= k&(-k)) res += ms[p][k];
return res;
}
int M = (L+R)/2;
int x = askms(x1, y1, x2, y2, 2*p, L, M);
int y = askms(x1, y1, x2, y2, 2*p+1, M+1, R);
return x+y;
}
void updateme(int x1, int y1, int x2, int y2, int dx)
{
updatems(x1, y1, y2+1, dx);
updatems(x2+1, y1, y2+1, -dx);
}
int askpong(int x, int y)
{
return askms(1, 1, x, y);
}
bool con(int a, int b)
{
return ask(a, b-1) == b-a;
}
void toggle(int x, int tim, bool upd)
{
int lo = 1, hi = x;
while(lo< hi)
{
int mid = (lo+hi)/2;
if(con(mid, x)) hi = mid;
else lo = mid+1;
}
int L = lo;
lo = x+1, hi = n+1;
while(lo< hi)
{
int mid = (lo+hi+1)/2;
if(con(x+1, mid)) lo = mid;
else hi = mid-1;
}
int R = lo;
if(!upd)
{
prep(L, x+1, x, R);
}
if(arr[x])
{
arr[x] = 0;
if(upd) updateme(L, x+1, x, R, tim);
}
else
{
arr[x] = 1;
if(upd) updateme(L, x+1, x, R, -tim);
// printf("go %d %d %d %d %d\n", L, x+1, x-1, R, -tim);
}
update(x, arr[x]);
}
int main()
{
scanf("%d %d", &n, &q);
scanf("%s", s+1);
for(int i = 1; i<= n; i++)
{
if(s[i] == '1')
{
update(i, 1);
arr[i] = 1;
}
}
for(int tim = 1; tim<= q; tim++)
{
A[tim] = B[tim] = -1;
char t[10];
scanf("%s", t+1);
if(t[1] == 't')
{
scanf("%d", &A[tim]);
}
else
{
scanf("%d %d", &A[tim], &B[tim]);
}
}
for(int tim = 1; tim<= q; tim++)
{
if(B[tim] == -1)
{
int x = A[tim];
toggle(x, tim, 0);
}
}
build();
memset(arr, 0, sizeof arr);
memset(st, 0, sizeof st);
for(int i = 1; i<= n; i++)
{
if(s[i] == '1')
{
update(i, 1);
arr[i] = 1;
}
}
for(int tim = 1; tim<= q; tim++)
{
if(B[tim] == -1)
{
int x = A[tim];
toggle(x, tim, 1);
continue;
}
int x = A[tim], y = B[tim];
bool cc = con(x, y);
if(cc) printf("%d\n", tim+askpong(x, y));
else printf("%d\n", askpong(x, y));
}
}