Submission #724529

#	Time	Username	Problem	Language	Result	Execution time	Memory
724529		n0sk1ll	Street Lamps (APIO19_street_lamps)	C++14	60 / 100	1359 ms	80272 KiB

street_lamps

#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];
    }
}

int lst[300005];
int zbir[300005];

void solvepoints(int n, string &s, int q, vector<pii> &qrys)
{
    int vremesad=0;
    for (auto it : qrys)
    {
        ++vremesad;
        if (it.xx==-1)
        {
            int i=it.yy-1;
            if (s[i]=='0') lst[i]=vremesad;
            else zbir[i]+=vremesad-lst[i];
            s[i]='0'+'1'-s[i];
        }
        else
        {
            int i=it.xx-1;
            if (s[i]=='1') cout<<zbir[i]+vremesad-lst[i]<<"\n";
            else cout<<zbir[i]<<"\n";
        }
    }
}

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 && (int)qrys.size()<=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

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20