oj.uz

Submission #133608

# Submission time Handle Problem Language Result Execution time Memory
133608 2019-07-21T06:26:31 Z discoverMeMe Street Lamps (APIO19_street_lamps) C++14
20 / 100
 3386 ms 524292 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 28536 KB Output is correct
2 Correct 56 ms 28536 KB Output is correct
3 Correct 56 ms 28536 KB Output is correct
4 Correct 58 ms 28792 KB Output is correct
5 Correct 58 ms 28792 KB Output is correct
6 Correct 52 ms 28536 KB Output is correct
7 Correct 60 ms 28796 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2051 ms 33216 KB Output is correct
2 Correct 2229 ms 34120 KB Output is correct
3 Correct 2799 ms 45860 KB Output is correct
4 Runtime error 1969 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 30968 KB Output is correct
2 Correct 72 ms 30972 KB Output is correct
3 Correct 74 ms 30968 KB Output is correct
4 Correct 75 ms 31116 KB Output is correct
5 Runtime error 3386 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 30456 KB Output is correct
2 Correct 68 ms 30584 KB Output is correct
3 Correct 74 ms 30712 KB Output is correct
4 Correct 77 ms 30712 KB Output is correct
5 Runtime error 2037 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 28536 KB Output is correct
2 Correct 56 ms 28536 KB Output is correct
3 Correct 56 ms 28536 KB Output is correct
4 Correct 58 ms 28792 KB Output is correct
5 Correct 58 ms 28792 KB Output is correct
6 Correct 52 ms 28536 KB Output is correct
7 Correct 60 ms 28796 KB Output is correct
8 Correct 2051 ms 33216 KB Output is correct
9 Correct 2229 ms 34120 KB Output is correct
10 Correct 2799 ms 45860 KB Output is correct
11 Runtime error 1969 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -