oj.uz

Submission #987631

# Submission time Handle Problem Language Result Execution time Memory
987631 2024-05-23T07:51:02 Z vivkostov Street Lamps (APIO19_street_lamps) C++14
60 / 100
 2966 ms 524288 KB 
#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
struct cell
{
    int l,r,st,in;
};
int n,q,l[3000005],r[3000005],br=2;
string s,a[3000005];
cell p[30000005];
map<pair<int,int>,int>m;
void checkmap()
{
    for(auto i=m.begin(); i!=m.end(); i++)
    {
        cout<<i->first.first<<" "<<i->first.second<<" "<<i->second;
        cout<<endl;
    }
    cout<<m.size()<<endl;
}
void update2(int l,int r,int ql,int qr,int h,int x)
{
    if(l>qr||r<qr)return;
    if(l==r&&r==qr)
    {
        p[h].st+=x;
        //cout<<l<<" "<<r<<" "<<p[h].st<<" : ";
        return;
    }
    if(!p[h].l)
    {
        p[h].l=br;
        p[h].r=br+1;
        br+=2;
    }
    int mi=(l+r)/2;
    update2(l,mi,ql,qr,p[h].l,x);
    update2(mi+1,r,ql,qr,p[h].r,x);
    p[h].st=p[p[h].l].st+p[p[h].r].st;
}
void update1(int l,int r,int ql,int qr,int h,int x)
{
    if(l>ql||r<ql)return;
    if(!p[h].l)
    {
        p[h].l=br;
        p[h].r=br+1;
        p[h].in=br+2;
        br+=3;
    }
    if(l==r&&r==ql)
    {
        //cout<<l<<" "<<r<<" "<<p[h].in<<" | ";
        update2(1,n,ql,qr,p[h].in,x);
        //cout<<endl;
        return;
    }
    int mi=(l+r)/2;
    update1(l,mi,ql,qr,p[h].l,x);
    update1(mi+1,r,ql,qr,p[h].r,x);
    //cout<<l<<" "<<r<<" "<<p[h].in<<" | ";
    update2(1,n,ql,qr,p[h].in,x);
    //cout<<endl;
}
int query2(int l,int r,int ql,int qr,int h)
{
    if(l>=qr)
    {
        return p[h].st;
    }
    if(r<qr||!p[h].l)return 0;
    int mi=(l+r)/2;
    return query2(l,mi,ql,qr,p[h].l)+query2(mi+1,r,ql,qr,p[h].r);
}
int query1(int l,int r,int ql,int qr,int h)
{
    if(l>ql||!p[h].l)return 0;
    if(r<=ql)
    {
        return query2(1,n,ql,qr,p[h].in);
    }
    int mi=(l+r)/2;
    return query1(l,mi,ql,qr,p[h].l)+query1(mi+1,r,ql,qr,p[h].r);
}
void remov(int in,int tim)
{
    pair<int,int>p;
    p.first=in;
    p.second=1000000000;
    auto it=m.upper_bound(p);
    int le,ri,st;
    it--;
    le=it->first.first,ri=it->first.second,st=it->second;
    update1(1,n,le,ri,1,tim-st);
    m.erase(it);
    if(in-1>=le)
    {
        p.first=le;
        p.second=in-1;
        m[p]=tim;
    }
    if(in+1<=ri)
    {
        p.first=in+1;
        p.second=ri;
        m[p]=tim;
    }
    s[in-1]='0';
    //checkmap();
}
void ad(int in,int tim)
{
    int lp=0,rp=0;
    pair<int,int>p;
    if(m.size()>0)
    {
        p.first=in;
        p.second=100000000;
        auto it=m.upper_bound(p);
        int le,ri,st;
        if(it!=m.begin())
        {
            it--;
            le=it->first.first,ri=it->first.second,st=it->second;
            //cout<<in<<" "<<le<<" "<<ri<<" "<<st<<endl;
            if(ri==in-1)
            {
                //cout<<in<<" ";
                update1(1,n,le,ri,1,tim-st);
                m.erase(it);
                lp=le;
            }
            it++;
        }
        if(it!=m.end())
        {
            it=m.upper_bound(p);
            le=it->first.first,ri=it->first.second,st=it->second;
            //cout<<in<<" "<<le<<" "<<ri<<" "<<st<<endl;
            if(le==in+1)
            {
                //cout<<in<<endl<<endl;
                update1(1,n,le,ri,1,tim-st);
                m.erase(it);
                rp=ri;
            }
        }
    }
    if(!lp)lp=in;
    if(!rp)rp=in;
    p.first=lp;
    p.second=rp;
    m[p]=tim;
    s[in-1]='1';
}
void print(int l,int r,int tim)
{
    if(m.size()==0)
    {
        cout<<query1(1,n,l,r,1)<<endl;
        return;
    }
    pair<int,int>p;
    p.first=l;
    p.second=100000000;
    auto it=m.upper_bound(p);
    if(it==m.begin())
    {
        cout<<query1(1,n,l,r,1)<<endl;
        return;
    }
    it--;
    int le=it->first.first;
    int ri=it->first.second;
    if(le<=l&&ri>=r)
    {
        cout<<query1(1,n,l,r,1)+tim-it->second<<endl;
        //cout<<query1(1,n,l,r,1)<<endl;
    }
    else cout<<query1(1,n,l,r,1)<<endl;
}
void newstart()
{
    for(int i=0; i<n; i++)
    {
        if(s[i]=='1')ad(i+1,1);
    }
}
void read()
{
    cin>>n>>q>>s;
    for(int i=1; i<=q; i++)
    {
        cin>>a[i]>>l[i];
        if(a[i]=="query")cin>>r[i];
    }
    newstart();
    for(int i=1; i<=q; i++)
    {
        /*if(i==6)
        {
            cout<<endl<<endl;
            checkmap();
            cout<<endl;
        }
        */
        if(a[i]=="toggle")
        {
            if(s[l[i]-1]=='0')ad(l[i],i+1);
            else remov(l[i],i+1);
        }
        else
        {
            print(l[i],r[i]-1,i+1);
        }
    }
}
int main()
{
    speed();
    read();
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 96852 KB Output is correct
2 Correct 38 ms 96860 KB Output is correct
3 Correct 38 ms 96848 KB Output is correct
4 Correct 36 ms 96860 KB Output is correct
5 Correct 40 ms 96860 KB Output is correct
6 Correct 39 ms 96856 KB Output is correct
7 Correct 37 ms 96860 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 99344 KB Output is correct
2 Correct 279 ms 99604 KB Output is correct
3 Correct 461 ms 107300 KB Output is correct
4 Correct 2320 ms 445416 KB Output is correct
5 Correct 2381 ms 510244 KB Output is correct
6 Correct 2514 ms 464936 KB Output is correct
7 Correct 112 ms 99280 KB Output is correct
8 Correct 1093 ms 288736 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 97628 KB Output is correct
2 Correct 40 ms 97760 KB Output is correct
3 Correct 40 ms 97628 KB Output is correct
4 Correct 40 ms 97108 KB Output is correct
5 Runtime error 2143 ms 524288 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 97276 KB Output is correct
2 Correct 42 ms 97368 KB Output is correct
3 Correct 39 ms 97368 KB Output is correct
4 Correct 40 ms 97472 KB Output is correct
5 Correct 799 ms 298696 KB Output is correct
6 Correct 1433 ms 398012 KB Output is correct
7 Correct 2160 ms 469276 KB Output is correct
8 Correct 2966 ms 524288 KB Output is correct
9 Correct 304 ms 102368 KB Output is correct
10 Correct 256 ms 101360 KB Output is correct
11 Correct 289 ms 102992 KB Output is correct
12 Correct 242 ms 101104 KB Output is correct
13 Correct 285 ms 102296 KB Output is correct
14 Correct 238 ms 100924 KB Output is correct
15 Correct 113 ms 105316 KB Output is correct
16 Correct 1172 ms 294652 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 96852 KB Output is correct
2 Correct 38 ms 96860 KB Output is correct
3 Correct 38 ms 96848 KB Output is correct
4 Correct 36 ms 96860 KB Output is correct
5 Correct 40 ms 96860 KB Output is correct
6 Correct 39 ms 96856 KB Output is correct
7 Correct 37 ms 96860 KB Output is correct
8 Correct 213 ms 99344 KB Output is correct
9 Correct 279 ms 99604 KB Output is correct
10 Correct 461 ms 107300 KB Output is correct
11 Correct 2320 ms 445416 KB Output is correct
12 Correct 2381 ms 510244 KB Output is correct
13 Correct 2514 ms 464936 KB Output is correct
14 Correct 112 ms 99280 KB Output is correct
15 Correct 1093 ms 288736 KB Output is correct
16 Correct 38 ms 97628 KB Output is correct
17 Correct 40 ms 97760 KB Output is correct
18 Correct 40 ms 97628 KB Output is correct
19 Correct 40 ms 97108 KB Output is correct
20 Runtime error 2143 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -