Submission #956936

#	Time	Username	Problem	Language	Result	Execution time	Memory
956936		HoriaHaivas	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	2807 ms	154160 KiB

street_lamps

/*
    "care a facut teste cu Lattice reduction attack e ciudat"
    "linistiti va putin"
    - 2023 -
*/
#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")

using namespace std;

struct event
{
    int x;
    int y;
    int moment;
};

int mom,n;
bool state[300005];
bool initialstate[300005];
bool type[300005];
int l[300005];
int r[300005];
int pos[300005];
int altaib[300005];
vector<event> updates;
vector<int> vals[300005];
vector<int> aib[300005];

void altupdate(int index, int delta)
{
    while (index<=n)
    {
        altaib[index]+=delta;
        index+=index&(-index);
    }
}

int altquery(int index)
{
    int ans;
    ans=0;
    while (index>0)
    {
        ans+=altaib[index];
        index-=index&(-index);
    }
    return ans;
}

void setupdate(int x, int y)
{
    for (; x<=n; x+=x&(-x))
    {
        vals[x].push_back(y);
    }
}

void updatinho(int apos)
{
    int st,dr,pas;
    if (state[apos]==1)
    {
        st=apos;
        pas=(1<<18);
        while (pas)
        {
            if (st-pas>0 && altquery(apos)-altquery(st-pas-1)==apos-(st-pas)+1)
                st-=pas;
            pas=pas/2;
        }
        dr=apos;
        pas=(1<<18);
        while (pas)
        {
            if (dr+pas<=n && altquery(dr+pas)-altquery(apos-1)==dr+pas-apos+1)
                dr+=pas;
            pas=pas/2;
        }
    }
    else
    {
        st=apos;
        pas=(1<<18);
        while (pas)
        {
            if (st-pas>0 && altquery(apos)-altquery(st-pas-1)==apos-(st-pas))
                st-=pas;
            pas=pas/2;
        }
        dr=apos;
        pas=(1<<18);
        while (pas)
        {
            if (dr+pas<=n && altquery(dr+pas)-altquery(apos-1)==dr+pas-apos)
                dr+=pas;
            pas=pas/2;
        }
    }
    setupdate(st,apos);
    updates.push_back({st,apos,mom});
    setupdate(apos+1,apos);
    updates.push_back({apos+1,apos,mom});
    setupdate(st,dr+1);
    updates.push_back({st,dr+1,mom});
    setupdate(apos+1,dr+1);
    updates.push_back({apos+1,dr+1,mom});
}

int indice(int x, int y)
{
    return upper_bound(vals[x].begin(),vals[x].end(),y)-vals[x].begin()-1;
}

void update(int x, int y, int delta)
{
    int newy;
    for (; x<=n; x+=x&(-x))
    {
        newy=indice(x,y);
        for (; newy<=aib[x].size(); newy+=newy&(-newy))
        {
            aib[x][newy]+=delta;
        }
    }
}

int query(int x, int y)
{
    int ans,newy;
    ans=0;
    for (; x>0; x-=x&(-x))
    {
        newy=indice(x,y);
        for (; newy>0; newy-=newy&(-newy))
        {
            ans+=aib[x][newy];
        }
    }
    return ans;
}

signed main()
{
    ifstream fin("secvp.in");
    ofstream fout("secvp.out");
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long q,i,j,cnt;
    char ch;
    string s;
    cin >> n >> q;
    for (i=1; i<=n; i++)
    {
        cin >> ch;
        if (ch=='0')
            state[i]=0;
        else
            state[i]=1;
        if (state[i]==1)
            altupdate(i,1);
        initialstate[i]=state[i];
    }
    for (i=1; i<=q; i++)
    {
        cin >> s;
        if (s=="query")
            type[i]=1;
        else
            type[i]=0;
        if (type[i]==1)
        {
            cin >> l[i] >> r[i];
        }
        else
        {
            cin >> pos[i];
            mom=i;
            updatinho(pos[i]);
            if (state[pos[i]]==1)
                altupdate(pos[i],-1);
            else
                altupdate(pos[i],1);
            state[pos[i]]=1-state[pos[i]];
        }
    }
    for (i=1; i<=n+1; i++)
    {
        altaib[i]=0;
        vals[i].push_back(0);
        sort(vals[i].begin(),vals[i].end());
        aib[i].resize(vals[i].size());
        state[i]=initialstate[i];
    }
    for (i=1;i<=n;i++)
    {
         if (state[i]==1)
            altupdate(i,1);
    }
    cnt=0;
    for (i=1; i<=q; i++)
    {
        if (type[i]==1)
        {
            if (altquery(r[i]-1)-altquery(l[i]-1)==(r[i]-l[i]))
                cout << i+query(l[i],r[i]-1) << "\n";
            else
                cout << query(l[i],r[i]-1) << "\n";
        }
        else
        {
            if (state[pos[i]]==1)
            {
                update(updates[cnt].x,updates[cnt].y,updates[cnt].moment);
                cnt++;
                update(updates[cnt].x,updates[cnt].y,-updates[cnt].moment);
                cnt++;
                update(updates[cnt].x,updates[cnt].y,-updates[cnt].moment);
                cnt++;
                update(updates[cnt].x,updates[cnt].y,updates[cnt].moment);
                cnt++;
                altupdate(pos[i],-1);
            }
            else
            {
                update(updates[cnt].x,updates[cnt].y,-updates[cnt].moment);
                cnt++;
                update(updates[cnt].x,updates[cnt].y,updates[cnt].moment);
                cnt++;
                update(updates[cnt].x,updates[cnt].y,updates[cnt].moment);
                cnt++;
                update(updates[cnt].x,updates[cnt].y,-updates[cnt].moment);
                cnt++;
                altupdate(pos[i],1);
            }
            state[pos[i]]=1-state[pos[i]];
        }
    }
}

Compilation message (stderr)

street_lamps.cpp: In function 'void update(int, int, int)':
street_lamps.cpp:123:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |         for (; newy<=aib[x].size(); newy+=newy&(-newy))
      |                ~~~~^~~~~~~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:152:19: warning: unused variable 'j' [-Wunused-variable]
  152 |     long long q,i,j,cnt;
      |                   ^

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