oj.uz

Submission #142664

# Submission time Handle Problem Language Result Execution time Memory
142664 2019-08-10T10:25:14 Z Bodo171 Street Lamps (APIO19_street_lamps) C++14
100 / 100
 2832 ms 287840 KB 
#include <iostream>
#include <fstream>
#include <set>
using namespace std;
const int nmax=300005;
struct pct
{
    int x,y,val;
}nl;
int n,i,q,j,poz,a,b;
string ini;
bool operator <(pct unu,pct doi)
{
    return unu.x<doi.x;
}
bool operator !=(pct unu,pct doi)
{
    return (unu.x!=doi.x||unu.y!=doi.y||unu.val!=doi.val);
}
struct node
{
    node *ls,*rs;
    int sum;
    node()
    {
        ls=rs=0;
        sum=0;
    }
};
set<pct> s;
set<pct>::iterator it;
string tip;
struct aint
{
    node *arb[nmax];
    int nr,stX,drX,stY,drY;
    void uY(node *nod,int l,int r,int poz,int val)
    {
        nod->sum+=val;
        if(l==r) return;
        int m=(l+r)/2;
        if(poz<=m)
        {
            if(!nod->ls)
                nod->ls=new node;
            uY(nod->ls,l,m,poz,val);
        }
        else
        {
            if(!nod->rs)
                nod->rs=new node;
            uY(nod->rs,m+1,r,poz,val);
        }
    }
    void qY(node *nod,int l,int r)
    {
        if(stY<=l&&r<=drY)
        {
            ret+=nod->sum;
            return;
        }
        int m=(l+r)/2;
        if(stY<=m&&nod->ls) qY(nod->ls,l,m);
        if(m<drY&&nod->rs)  qY(nod->rs,m+1,r);
    }
    int ret;
    inline int lbit(int x)
    {
        return ((x^(x-1))&x);
    }
    void query(int x,int y)
    {
        for(int idx=x;idx>0;idx-=lbit(idx))
            qY(arb[idx],1,n);
    }
    void update(int x,int y,int val)
    {
        for(int idx=x;idx<=n;idx+=lbit(idx))
            uY(arb[idx],1,n,y,val);
    }
    int Q(int x,int y)
    {
        ret=0;
        stY=y;drY=n;
        query(x,y);
        return ret;
    }
    void ini()
    {
        for(i=1;i<=n;i++)
            arb[i]=new node;
    }
}A;
void ins(int poz)
{
    pct st=nl,dr=nl,act;
    it=s.lower_bound({poz,0,0});
    if((*it).x==poz+1)
        dr=(*it);
    if(it!=s.begin())
    {
        it--;
        if((*it).y==poz-1)
            st=(*it);
    }
    act.val=i;act.x=act.y=poz;
    if(st!=nl)
    {
        A.update(st.x,st.y,i-st.val);
        act.x=st.x;
        s.erase(st);
    }
    if(dr!=nl)
    {
        A.update(dr.x,dr.y,i-dr.val);
        act.y=dr.y;
        s.erase(dr);
    }
    s.insert(act);
    return;
}
void del(int poz)
{
    pct st=nl,dr=nl,act;
    it=s.lower_bound({poz+1,0,0});
    it--;//mereu se poate
    act=(*it);
    A.update(act.x,act.y,i-act.val);
    s.erase(act);
    if(poz>act.x)
    {
        st={act.x,poz-1,i};
        s.insert(st);
    }
    if(poz<act.y)
    {
        dr={poz+1,act.y,i};
        s.insert(dr);
    }

}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>q;
    cin>>ini;
    ini=" "+ini;
    for(i=1;i<ini.size();i++)
    {
        if(ini[i]=='1')
        {
            j=i;
            while(j<ini.size()&&ini[j]=='1')
                j++;
            j--;
            s.insert({i,j,0});
            i=j;
        }
    }
    A.ini();
    for(i=1;i<=q;i++)
    {
        cin>>tip;
        if(tip=="toggle")
        {
            cin>>poz;
            if(ini[poz]=='1')
            {
                ini[poz]='0';
                del(poz);
            }
            else
            {
                ini[poz]='1';
                ins(poz);
            }
        }
        else
        {
            int ans;
            cin>>a>>b;
            it=s.lower_bound({b,0,0});
            ans=0;
            if(it!=s.begin())
            {
                it--;
                if((*it).x<=a&&(*it).y>=b-1) ans=i-(*it).val;
            }
            ans+=A.Q(a,b-1);
            cout<<ans<<'\n';
        }
    }
    return 0;
}

Compilation message

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:149:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=1;i<ini.size();i++)
             ~^~~~~~~~~~~
street_lamps.cpp:154:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(j<ini.size()&&ini[j]=='1')
                   ~^~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 599 ms 4552 KB Output is correct
2 Correct 654 ms 5224 KB Output is correct
3 Correct 1020 ms 11128 KB Output is correct
4 Correct 2548 ms 195524 KB Output is correct
5 Correct 2832 ms 219752 KB Output is correct
6 Correct 2459 ms 211372 KB Output is correct
7 Correct 1022 ms 13480 KB Output is correct
8 Correct 1045 ms 14680 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 888 KB Output is correct
2 Correct 5 ms 888 KB Output is correct
3 Correct 6 ms 760 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 2491 ms 287840 KB Output is correct
6 Correct 2708 ms 274252 KB Output is correct
7 Correct 2367 ms 224268 KB Output is correct
8 Correct 1035 ms 20452 KB Output is correct
9 Correct 736 ms 4084 KB Output is correct
10 Correct 797 ms 4408 KB Output is correct
11 Correct 802 ms 4804 KB Output is correct
12 Correct 1016 ms 19068 KB Output is correct
13 Correct 1035 ms 20408 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 4 ms 760 KB Output is correct
4 Correct 4 ms 760 KB Output is correct
5 Correct 1329 ms 27632 KB Output is correct
6 Correct 1753 ms 152692 KB Output is correct
7 Correct 2189 ms 210868 KB Output is correct
8 Correct 2474 ms 257260 KB Output is correct
9 Correct 446 ms 1128 KB Output is correct
10 Correct 207 ms 708 KB Output is correct
11 Correct 446 ms 1312 KB Output is correct
12 Correct 210 ms 632 KB Output is correct
13 Correct 439 ms 1004 KB Output is correct
14 Correct 207 ms 504 KB Output is correct
15 Correct 1029 ms 13204 KB Output is correct
16 Correct 1038 ms 14476 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 599 ms 4552 KB Output is correct
9 Correct 654 ms 5224 KB Output is correct
10 Correct 1020 ms 11128 KB Output is correct
11 Correct 2548 ms 195524 KB Output is correct
12 Correct 2832 ms 219752 KB Output is correct
13 Correct 2459 ms 211372 KB Output is correct
14 Correct 1022 ms 13480 KB Output is correct
15 Correct 1045 ms 14680 KB Output is correct
16 Correct 4 ms 888 KB Output is correct
17 Correct 5 ms 888 KB Output is correct
18 Correct 6 ms 760 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 2491 ms 287840 KB Output is correct
21 Correct 2708 ms 274252 KB Output is correct
22 Correct 2367 ms 224268 KB Output is correct
23 Correct 1035 ms 20452 KB Output is correct
24 Correct 736 ms 4084 KB Output is correct
25 Correct 797 ms 4408 KB Output is correct
26 Correct 802 ms 4804 KB Output is correct
27 Correct 1016 ms 19068 KB Output is correct
28 Correct 1035 ms 20408 KB Output is correct
29 Correct 5 ms 376 KB Output is correct
30 Correct 5 ms 632 KB Output is correct
31 Correct 4 ms 760 KB Output is correct
32 Correct 4 ms 760 KB Output is correct
33 Correct 1329 ms 27632 KB Output is correct
34 Correct 1753 ms 152692 KB Output is correct
35 Correct 2189 ms 210868 KB Output is correct
36 Correct 2474 ms 257260 KB Output is correct
37 Correct 446 ms 1128 KB Output is correct
38 Correct 207 ms 708 KB Output is correct
39 Correct 446 ms 1312 KB Output is correct
40 Correct 210 ms 632 KB Output is correct
41 Correct 439 ms 1004 KB Output is correct
42 Correct 207 ms 504 KB Output is correct
43 Correct 1029 ms 13204 KB Output is correct
44 Correct 1038 ms 14476 KB Output is correct
45 Correct 345 ms 2836 KB Output is correct
46 Correct 393 ms 2960 KB Output is correct
47 Correct 1140 ms 81936 KB Output is correct
48 Correct 2083 ms 199740 KB Output is correct
49 Correct 900 ms 4760 KB Output is correct
50 Correct 902 ms 4640 KB Output is correct
51 Correct 899 ms 4652 KB Output is correct
52 Correct 907 ms 5112 KB Output is correct
53 Correct 904 ms 5112 KB Output is correct
54 Correct 900 ms 5036 KB Output is correct