oj.uz

Submission #142663

# Submission time Handle Problem Language Result Execution time Memory
142663 2019-08-10T10:18:10 Z Bodo171 Street Lamps (APIO19_street_lamps) C++14
60 / 100
 4135 ms 524292 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[4*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);
    }
    void update(int nod,int l,int r,int x,int y,int val)
    {
        uY(arb[nod],1,n,y,val);
        if(l==r) return;
        int m=(l+r)/2;
        if(x<=m) update(2*nod,l,m,x,y,val);
        else update(2*nod+1,m+1,r,x,y,val);
    }
    int ret;
    void query(int nod,int l,int r)
    {
        if(stX<=l&&r<=drX)
        {
            qY(arb[nod],1,n);
            return;
        }
        int m=(l+r)/2;
        if(stX<=m) query(2*nod,l,m);
        if(m<drX)  query(2*nod+1,m+1,r);
    }
    int Q(int x,int y)
    {
        ret=0;
        stX=1;drX=x;stY=y;drY=n;
        query(1,1,n);
        return ret;
    }
    void build(int nod,int l,int r)
    {
        arb[nod]=new node;
        if(l==r) return;
        int m=(l+r)/2;
        build(2*nod,l,m);
        build(2*nod+1,m+1,r);
    }
}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(1,1,n,st.x,st.y,i-st.val);
        act.x=st.x;
        s.erase(st);
    }
    if(dr!=nl)
    {
        A.update(1,1,n,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(1,1,n,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.build(1,1,n);
    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:157:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=1;i<ini.size();i++)
             ~^~~~~~~~~~~
street_lamps.cpp:162: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 380 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 663 ms 1596 KB Output is correct
2 Correct 758 ms 5644 KB Output is correct
3 Correct 1281 ms 16856 KB Output is correct
4 Correct 3402 ms 387920 KB Output is correct
5 Correct 4078 ms 442900 KB Output is correct
6 Correct 3822 ms 419344 KB Output is correct
7 Correct 1160 ms 34496 KB Output is correct
8 Correct 1189 ms 35680 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1528 KB Output is correct
2 Correct 6 ms 1400 KB Output is correct
3 Correct 7 ms 1148 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Runtime error 3720 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 6 ms 912 KB Output is correct
3 Correct 6 ms 1144 KB Output is correct
4 Correct 5 ms 1244 KB Output is correct
5 Correct 1533 ms 58416 KB Output is correct
6 Correct 2600 ms 305016 KB Output is correct
7 Correct 3217 ms 419004 KB Output is correct
8 Correct 4135 ms 510652 KB Output is correct
9 Correct 547 ms 4984 KB Output is correct
10 Correct 266 ms 3448 KB Output is correct
11 Correct 540 ms 4988 KB Output is correct
12 Correct 266 ms 3660 KB Output is correct
13 Correct 552 ms 5112 KB Output is correct
14 Correct 267 ms 3636 KB Output is correct
15 Correct 1194 ms 34296 KB Output is correct
16 Correct 1153 ms 35684 KB Output is correct

Subtask #5
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 380 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 663 ms 1596 KB Output is correct
9 Correct 758 ms 5644 KB Output is correct
10 Correct 1281 ms 16856 KB Output is correct
11 Correct 3402 ms 387920 KB Output is correct
12 Correct 4078 ms 442900 KB Output is correct
13 Correct 3822 ms 419344 KB Output is correct
14 Correct 1160 ms 34496 KB Output is correct
15 Correct 1189 ms 35680 KB Output is correct
16 Correct 4 ms 1528 KB Output is correct
17 Correct 6 ms 1400 KB Output is correct
18 Correct 7 ms 1148 KB Output is correct
19 Correct 6 ms 376 KB Output is correct
20 Runtime error 3720 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -