oj.uz

Submission #987632

# Submission time Handle Problem Language Result Execution time Memory
987632 2024-05-23T07:52:18 Z vivkostov Street Lamps (APIO19_street_lamps) C++14
60 / 100
 3085 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);
            if(it!=m.end())
            {
                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 37 ms 96852 KB Output is correct
2 Correct 35 ms 96848 KB Output is correct
3 Correct 40 ms 96768 KB Output is correct
4 Correct 39 ms 96860 KB Output is correct
5 Correct 38 ms 96860 KB Output is correct
6 Correct 38 ms 96860 KB Output is correct
7 Correct 40 ms 96860 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 99408 KB Output is correct
2 Correct 276 ms 99788 KB Output is correct
3 Correct 482 ms 107344 KB Output is correct
4 Correct 2015 ms 445392 KB Output is correct
5 Correct 2611 ms 510388 KB Output is correct
6 Correct 2081 ms 464516 KB Output is correct
7 Correct 113 ms 99304 KB Output is correct
8 Correct 1100 ms 288488 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 97632 KB Output is correct
2 Correct 40 ms 97628 KB Output is correct
3 Correct 39 ms 97624 KB Output is correct
4 Correct 40 ms 97108 KB Output is correct
5 Runtime error 2344 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 36 ms 97052 KB Output is correct
2 Correct 42 ms 97436 KB Output is correct
3 Correct 41 ms 97592 KB Output is correct
4 Correct 41 ms 97544 KB Output is correct
5 Correct 746 ms 299080 KB Output is correct
6 Correct 1799 ms 398300 KB Output is correct
7 Correct 2005 ms 464068 KB Output is correct
8 Correct 3085 ms 522872 KB Output is correct
9 Correct 290 ms 99200 KB Output is correct
10 Correct 245 ms 98116 KB Output is correct
11 Correct 286 ms 99152 KB Output is correct
12 Correct 242 ms 98252 KB Output is correct
13 Correct 293 ms 99000 KB Output is correct
14 Correct 248 ms 98232 KB Output is correct
15 Correct 110 ms 99304 KB Output is correct
16 Correct 1140 ms 288516 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 96852 KB Output is correct
2 Correct 35 ms 96848 KB Output is correct
3 Correct 40 ms 96768 KB Output is correct
4 Correct 39 ms 96860 KB Output is correct
5 Correct 38 ms 96860 KB Output is correct
6 Correct 38 ms 96860 KB Output is correct
7 Correct 40 ms 96860 KB Output is correct
8 Correct 212 ms 99408 KB Output is correct
9 Correct 276 ms 99788 KB Output is correct
10 Correct 482 ms 107344 KB Output is correct
11 Correct 2015 ms 445392 KB Output is correct
12 Correct 2611 ms 510388 KB Output is correct
13 Correct 2081 ms 464516 KB Output is correct
14 Correct 113 ms 99304 KB Output is correct
15 Correct 1100 ms 288488 KB Output is correct
16 Correct 40 ms 97632 KB Output is correct
17 Correct 40 ms 97628 KB Output is correct
18 Correct 39 ms 97624 KB Output is correct
19 Correct 40 ms 97108 KB Output is correct
20 Runtime error 2344 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -