oj.uz

Submission #987634

# Submission time Handle Problem Language Result Execution time Memory
987634 2024-05-23T07:57:01 Z vivkostov Street Lamps (APIO19_street_lamps) C++14
100 / 100
 2814 ms 471020 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,r,br=2;
string s,a;
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;
            }
        }
        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;
    newstart();
    for(int i=1; i<=q; i++)
    {
        cin>>a>>l;
        if(a=="toggle")
        {
            if(s[l-1]=='0')ad(l,i+1);
            else remov(l,i+1);
        }
        else
        {
            cin>>r;
            print(l,r-1,i+1);
        }
    }
}
int main()
{
    speed();
    read();
    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 1328 KB Output is correct
2 Correct 231 ms 1620 KB Output is correct
3 Correct 424 ms 9300 KB Output is correct
4 Correct 2108 ms 347560 KB Output is correct
5 Correct 2523 ms 412320 KB Output is correct
6 Correct 2033 ms 366720 KB Output is correct
7 Correct 79 ms 1412 KB Output is correct
8 Correct 1025 ms 190760 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1372 KB Output is correct
2 Correct 3 ms 1372 KB Output is correct
3 Correct 3 ms 1368 KB Output is correct
4 Correct 3 ms 2652 KB Output is correct
5 Correct 2400 ms 471020 KB Output is correct
6 Correct 2481 ms 461204 KB Output is correct
7 Correct 2690 ms 416740 KB Output is correct
8 Correct 1118 ms 196632 KB Output is correct
9 Correct 73 ms 3924 KB Output is correct
10 Correct 75 ms 4436 KB Output is correct
11 Correct 88 ms 4656 KB Output is correct
12 Correct 79 ms 7172 KB Output is correct
13 Correct 1091 ms 196584 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 3 ms 860 KB Output is correct
3 Correct 2 ms 1112 KB Output is correct
4 Correct 5 ms 1368 KB Output is correct
5 Correct 779 ms 200892 KB Output is correct
6 Correct 1335 ms 300204 KB Output is correct
7 Correct 1998 ms 366060 KB Output is correct
8 Correct 2814 ms 423780 KB Output is correct
9 Correct 253 ms 1260 KB Output is correct
10 Correct 205 ms 584 KB Output is correct
11 Correct 249 ms 1160 KB Output is correct
12 Correct 205 ms 592 KB Output is correct
13 Correct 254 ms 2704 KB Output is correct
14 Correct 210 ms 836 KB Output is correct
15 Correct 90 ms 1256 KB Output is correct
16 Correct 1075 ms 190736 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 172 ms 1328 KB Output is correct
9 Correct 231 ms 1620 KB Output is correct
10 Correct 424 ms 9300 KB Output is correct
11 Correct 2108 ms 347560 KB Output is correct
12 Correct 2523 ms 412320 KB Output is correct
13 Correct 2033 ms 366720 KB Output is correct
14 Correct 79 ms 1412 KB Output is correct
15 Correct 1025 ms 190760 KB Output is correct
16 Correct 3 ms 1372 KB Output is correct
17 Correct 3 ms 1372 KB Output is correct
18 Correct 3 ms 1368 KB Output is correct
19 Correct 3 ms 2652 KB Output is correct
20 Correct 2400 ms 471020 KB Output is correct
21 Correct 2481 ms 461204 KB Output is correct
22 Correct 2690 ms 416740 KB Output is correct
23 Correct 1118 ms 196632 KB Output is correct
24 Correct 73 ms 3924 KB Output is correct
25 Correct 75 ms 4436 KB Output is correct
26 Correct 88 ms 4656 KB Output is correct
27 Correct 79 ms 7172 KB Output is correct
28 Correct 1091 ms 196584 KB Output is correct
29 Correct 2 ms 604 KB Output is correct
30 Correct 3 ms 860 KB Output is correct
31 Correct 2 ms 1112 KB Output is correct
32 Correct 5 ms 1368 KB Output is correct
33 Correct 779 ms 200892 KB Output is correct
34 Correct 1335 ms 300204 KB Output is correct
35 Correct 1998 ms 366060 KB Output is correct
36 Correct 2814 ms 423780 KB Output is correct
37 Correct 253 ms 1260 KB Output is correct
38 Correct 205 ms 584 KB Output is correct
39 Correct 249 ms 1160 KB Output is correct
40 Correct 205 ms 592 KB Output is correct
41 Correct 254 ms 2704 KB Output is correct
42 Correct 210 ms 836 KB Output is correct
43 Correct 90 ms 1256 KB Output is correct
44 Correct 1075 ms 190736 KB Output is correct
45 Correct 64 ms 2640 KB Output is correct
46 Correct 110 ms 2900 KB Output is correct
47 Correct 899 ms 134892 KB Output is correct
48 Correct 2215 ms 352536 KB Output is correct
49 Correct 100 ms 4692 KB Output is correct
50 Correct 79 ms 4448 KB Output is correct
51 Correct 86 ms 4692 KB Output is correct
52 Correct 88 ms 4980 KB Output is correct
53 Correct 84 ms 4948 KB Output is correct
54 Correct 89 ms 5204 KB Output is correct