Submission #133608

#	Time	Username	Problem	Language	Result	Execution time	Memory
133608		discoverMeMe	가로등 (APIO19_street_lamps)	C++14	20 / 100	3386 ms	524292 KiB

street_lamps

#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#define fori(a,b) for(int i=a;i<b;i++)
#define forj(a,b) for(int j=a;j<b;j++)
#define fork(a,b) for(int k=a;k<b;k++)
#define ford(i,a,b) for(int i=a;i>=b;i--)
#define seto(x,i) memset(x,i,sizeof x)
#define inf 0x3f3f3f3f;
#define INF 0x3f3f3f3f3f3f3f3f;
#define pf first
#define ps second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

struct node
{
    int l,r,m,b,lc,rc;
};

const int N=3e5+1;

class segTree
{
public:
    vector<node> seg; //4*NN if NN is not a power of 2
    int sz;
    segTree()
    {
        build();
    }
    void build()
    {
        sz=1; seg.push_back({0,0,0,0,0,0});
        seg.push_back({1,N,0,0,0,0});
    }
    void birth(int num)
    {
        if(seg[num].lc!=0)
            return;
        int mid=(seg[num].l+seg[num].r)/2;
        seg[num].lc=++sz;
        seg.push_back({seg[num].l,mid,seg[num].m,seg[num].b,0,0});
        seg[num].rc=++sz;
        seg.push_back({mid+1,seg[num].r,seg[num].m,seg[num].b,0,0});
    }
    void update(int pos,int m,int b)
    {
        update(pos,m,b,1);
    }
    void update(int pos,int m,int b,int num)
    {
        if(seg[num].l==pos&&seg[num].r==pos)
        {
            seg[num].m+=m;
            seg[num].b+=b;
            return;
        }
        birth(num);
        int mid=(seg[num].l+seg[num].r)/2;
        if(pos<=mid)
            update(pos,m,b,seg[num].lc);
        else
            update(pos,m,b,seg[num].rc);
        seg[num].m=seg[seg[num].lc].m+seg[seg[num].rc].m;
        seg[num].b=seg[seg[num].lc].b+seg[seg[num].rc].b;
    }
    pii query(int l,int r)
    {
        return query(l,r,1);
    }
    pii query(int l,int r,int num)
    {
        if((seg[num].l==l&&seg[num].r==r)||seg[num].lc==0)
            return {seg[num].m,seg[num].b};
        int mid=(seg[num].l+seg[num].r)/2;
        if(r<=mid)
            return query(l,r,seg[num].lc);
        if(l>mid)
            return query(l,r,seg[num].rc);
        pii temp1=query(l,mid,seg[num].lc), temp2=query(mid+1,r,seg[num].rc);
        return {temp1.pf+temp2.pf,temp1.ps+temp2.ps};
    }
};
segTree tree[N];

class biTree
{
    public:
    biTree()
    {
        //fori(1,N)
          //  tree[i].build();
    }
    void add(int x,int y,int m,int b)
    {
        while(x<N)
        {
            tree[x].update(y,m,b);
            x+=(x&(-x));
        }
    }
    pii addto(int x,int y)
    {
        pii sum;
        while(x>0)
        {
            pii temp=tree[x].query(1,y);
            sum.pf+=temp.pf; sum.ps+=temp.ps;
            x-=(x&(-x));
        }
        return sum;
    }
};
biTree bit;

set<int> z0;
int n,q,a,b,x,y;
string in;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>q>>in;
    fori(0,n+2)
        z0.insert(i);
    fori(1,n+1)
        if(in[i-1]=='1')
        {
            a=*prev(z0.find(i),1)+1;
            b=*next(z0.find(i),1)-1;
            bit.add(a,i,1,0);
            bit.add(i+1,i,-1,0);
            bit.add(a,b+1,-1,0);
            bit.add(i+1,b+1,1,0);
            z0.erase(i);
        }
    fori(1,q+1)
    {
        cin>>in;
        if(in=="toggle")
        {
            cin>>x;
            if(z0.count(x))
            {
                a=*prev(z0.find(x),1)+1;
                b=*next(z0.find(x),1)-1;
                bit.add(a,x,1,-i);
                bit.add(x+1,x,-1,i);
                bit.add(a,b+1,-1,i);
                bit.add(x+1,b+1,1,-i);
                z0.erase(x);
            }
            else
            {
                z0.insert(x);
                a=*prev(z0.find(x),1)+1;
                b=*next(z0.find(x),1)-1;
                bit.add(a,x,-1,i);
                bit.add(x+1,x,1,-i);
                bit.add(a,b+1,1,-i);
                bit.add(x+1,b+1,-1,i);
            }
        }
        else
        {
            cin>>x>>y; y--;
            pii temp=bit.addto(x,y);
            cout<<temp.pf*i+temp.ps<<"\n";
        }
    }
    return 0;
}
/* idea how to solve:
binary index tree OF segtrees
space saving segtrees - only store necessary nodes
each node contains index of child nodes, only allocate child when needed

each bit cell is a segtree
for example 2nd segtree contains sum of 1st and 2nd row
when doing range query do the bit method but for every cell you go to get the value of that cell by doing segtree query

store set of all broken lamps
each query l to r is a point (l,r) on the bit segtree
when a lamp is fixed at time i route from all the place on left of lamp become connected to right, total time add t-i+1
when lamp broken routes disconnected, total time minus t-i+1
so update a rectangle in the bit segtree
bit segtree stores m=the total number of ts and b=sum of all i+1s
when query l to r go to cell (l,r) and get answer=t*m+b

store difference instead of values - when getting value of a cell, find sum from (0,0) to (x,y)
*/

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