oj.uz

Submission #758460

# Submission time Handle Problem Language Result Execution time Memory
758460 2023-06-14T16:07:44 Z bgnbvnbv Street Lamps (APIO19_street_lamps) C++14
100 / 100
 856 ms 134208 KB 
#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=int;
const ll maxN=3e5+10;
///const ll inf=1e18;
const ll mod=1e9+7;
ll n;
struct off2dseg
{
    struct BIT
    {
        vector<ll> bit;
        void upd(ll pos,ll val)
        {
            while(pos<bit.size())
            {
                bit[pos]+=val;
                pos+=pos&(-pos);
            }
        }
        ll get(ll i)
        {
            ll ans=0;
            while(i>0)
            {
                ans+=bit[i];
                i-=i&(-i);
            }
            return ans;
        }
    }bit[4*maxN];
    vector<ll>vec[4*maxN];
    void fupdate(ll x1,ll y1,ll x2,ll y2,ll id=1,ll l=1,ll r=n)
    {
        if(x2<l||r<x1) return;
        if(x1<=l&&r<=x2)
        {
            vec[id].pb(y1);
            vec[id].pb(y2+1);
            return;
        }
        ll mid=l+r>>1;
        fupdate(x1,y1,x2,y2,id*2,l,mid);
        fupdate(x1,y1,x2,y2,id*2+1,mid+1,r);
    }
    void build()
    {
        for(int i=1;i<=4*n;i++)
        {
            sort(vec[i].begin(),vec[i].end());
            bit[i].bit.resize(vec[i].size()+1);
        }
    }
    void update(ll x1,ll y1,ll x2,ll y2,ll v,ll id=1,ll l=1,ll r=n)
    {
        if(x2<l||r<x1) return;
        if(x1<=l&&r<=x2)
        {
            y1=lower_bound(vec[id].begin(),vec[id].end(),y1)-vec[id].begin()+1;
            y2=lower_bound(vec[id].begin(),vec[id].end(),y2+1)-vec[id].begin()+1;
            bit[id].upd(y1,v);
            bit[id].upd(y2,-v);
            return;
        }
        ll mid=l+r>>1;
        update(x1,y1,x2,y2,v,id*2,l,mid);
        update(x1,y1,x2,y2,v,id*2+1,mid+1,r);
    }
    ll get(ll x,ll y,ll id=1,ll l=1,ll r=n)
    {
        ll p=upper_bound(vec[id].begin(),vec[id].end(),y)-vec[id].begin();
        p=bit[id].get(p);
        if(l==r) return p;
        ll mid=l+r>>1;
        if(x<=mid) return p+get(x,y,id*2,l,mid);
        else return p+get(x,y,id*2+1,mid+1,r);
    }
}tree;
set<int> s;
ll q;
char c[maxN];
ll a[maxN],r[maxN],t[maxN];
string T[maxN];
struct qq
{
    ll i,l,r,v;
};
vector<qq> quer;
set<int> ::iterator it;
ll x[maxN],y[maxN];
ll ans[maxN];
void solve()
{
    cin >> n >> q ;
    for(int i=1;i<=n;i++)
    {
        cin >> c[i];
        a[i]=c[i]-'0';
    }
    for(int i=1;i<=n;i++)
    {
        ll j=i;
        if(a[i]==0) continue;
        while(j<=n&&a[j]==a[i])
        {
            j++;
        }
        s.insert(i);
        r[i]=j-1;
        t[i]=0;
        i=j-1;
    }
    for(int i=1;i<=q;i++)
    {
        cin >> T[i];
        if(T[i]=="toggle")
        {
            ll p;
            cin >> p;
            if(a[p]==1)
            {
                it=s.upper_bound(p);
                it--;
                ll L=*it;
                ll R=r[L];
                ll T=t[L];
                s.erase(it);
                tree.fupdate(L,L,R,R);
                quer.pb({i,L,R,i-T});
                if(L<=p-1)
                {
                    r[L]=p-1;
                    t[L]=i;
                    s.insert(L);
                }
                if(p+1<=R)
                {
                    r[p+1]=R;
                    t[p+1]=i;
                    s.insert(p+1);
                }
            }
            else
            {
                it=s.lower_bound(p);
                ll L=p,R=p;
                vector<ll> xoa;
                if(it!=s.end()&&*it==p+1)
                {
                    tree.fupdate(p+1,p+1,r[p+1],r[p+1]);
                    R=r[p+1];
                    quer.pb({i,p+1,r[p+1],i-t[p+1]});
                    xoa.pb(p+1);
                }
                if(it!=s.begin())
                {
                    it--;
                    if(r[*it]==p-1)
                    {
                        tree.fupdate(*it,*it,p-1,p-1);
                        L=*it;
                        quer.pb({i,L,p-1,i-t[L]});
                        xoa.pb(L);
                    }
                }
                for(auto zz:xoa) s.erase(zz);
                r[L]=R;
                t[L]=i;
                s.insert(L);
            }
            a[p]^=1;
        }
        else
        {
            cin >> x[i] >> y[i];
            y[i]--;
            it=s.upper_bound(y[i]);
            if(it!=s.begin()&&a[y[i]]==1)
            {
                it--;
                if(*it<=x[i])
                {
                    ans[i]+=i-t[*it];
                }
            }
        }
    }
    //cout << ans[4]<<'\n';
    tree.build();
    ll j=0;
    for(int i=1;i<=q;i++)
    {
        while(j<quer.size()&&quer[j].i<=i)
        {
            ll L=quer[j].l;
            ll R=quer[j].r;
            ll v=quer[j].v;
            tree.update(L,L,R,R,v);
            j++;
        }
        if(T[i]=="query")
        {

            ans[i]+=tree.get(x[i],y[i]);
            cout << ans[i]<<'\n';
        }
    }
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message

street_lamps.cpp: In member function 'void off2dseg::BIT::upd(ll, ll)':
street_lamps.cpp:21:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |             while(pos<bit.size())
      |                   ~~~^~~~~~~~~~~
street_lamps.cpp: In member function 'void off2dseg::fupdate(ll, ll, ll, ll, ll, ll, ll)':
street_lamps.cpp:48:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |         ll mid=l+r>>1;
      |                ~^~
street_lamps.cpp: In member function 'void off2dseg::update(ll, ll, ll, ll, ll, ll, ll, ll)':
street_lamps.cpp:71:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |         ll mid=l+r>>1;
      |                ~^~
street_lamps.cpp: In member function 'll off2dseg::get(ll, ll, ll, ll, ll)':
street_lamps.cpp:80:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |         ll mid=l+r>>1;
      |                ~^~
street_lamps.cpp: In function 'void solve()':
street_lamps.cpp:199:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<qq>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  199 |         while(j<quer.size()&&quer[j].i<=i)
      |               ~^~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 66004 KB Output is correct
2 Correct 30 ms 66076 KB Output is correct
3 Correct 31 ms 65996 KB Output is correct
4 Correct 32 ms 66008 KB Output is correct
5 Correct 30 ms 66132 KB Output is correct
6 Correct 31 ms 66084 KB Output is correct
7 Correct 33 ms 66108 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 77360 KB Output is correct
2 Correct 257 ms 81072 KB Output is correct
3 Correct 317 ms 82424 KB Output is correct
4 Correct 604 ms 128320 KB Output is correct
5 Correct 809 ms 131624 KB Output is correct
6 Correct 635 ms 127704 KB Output is correct
7 Correct 251 ms 115076 KB Output is correct
8 Correct 248 ms 116472 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 66312 KB Output is correct
2 Correct 34 ms 66232 KB Output is correct
3 Correct 35 ms 66252 KB Output is correct
4 Correct 37 ms 66228 KB Output is correct
5 Correct 840 ms 134208 KB Output is correct
6 Correct 856 ms 133872 KB Output is correct
7 Correct 779 ms 130952 KB Output is correct
8 Correct 253 ms 116636 KB Output is correct
9 Correct 114 ms 72524 KB Output is correct
10 Correct 130 ms 73148 KB Output is correct
11 Correct 126 ms 73428 KB Output is correct
12 Correct 257 ms 115184 KB Output is correct
13 Correct 266 ms 116676 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 66248 KB Output is correct
2 Correct 33 ms 66260 KB Output is correct
3 Correct 33 ms 66312 KB Output is correct
4 Correct 34 ms 66224 KB Output is correct
5 Correct 357 ms 121292 KB Output is correct
6 Correct 509 ms 124408 KB Output is correct
7 Correct 614 ms 126944 KB Output is correct
8 Correct 821 ms 130352 KB Output is correct
9 Correct 282 ms 81328 KB Output is correct
10 Correct 280 ms 82464 KB Output is correct
11 Correct 290 ms 81236 KB Output is correct
12 Correct 296 ms 82500 KB Output is correct
13 Correct 289 ms 81200 KB Output is correct
14 Correct 297 ms 82444 KB Output is correct
15 Correct 249 ms 115148 KB Output is correct
16 Correct 255 ms 116512 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 66004 KB Output is correct
2 Correct 30 ms 66076 KB Output is correct
3 Correct 31 ms 65996 KB Output is correct
4 Correct 32 ms 66008 KB Output is correct
5 Correct 30 ms 66132 KB Output is correct
6 Correct 31 ms 66084 KB Output is correct
7 Correct 33 ms 66108 KB Output is correct
8 Correct 231 ms 77360 KB Output is correct
9 Correct 257 ms 81072 KB Output is correct
10 Correct 317 ms 82424 KB Output is correct
11 Correct 604 ms 128320 KB Output is correct
12 Correct 809 ms 131624 KB Output is correct
13 Correct 635 ms 127704 KB Output is correct
14 Correct 251 ms 115076 KB Output is correct
15 Correct 248 ms 116472 KB Output is correct
16 Correct 33 ms 66312 KB Output is correct
17 Correct 34 ms 66232 KB Output is correct
18 Correct 35 ms 66252 KB Output is correct
19 Correct 37 ms 66228 KB Output is correct
20 Correct 840 ms 134208 KB Output is correct
21 Correct 856 ms 133872 KB Output is correct
22 Correct 779 ms 130952 KB Output is correct
23 Correct 253 ms 116636 KB Output is correct
24 Correct 114 ms 72524 KB Output is correct
25 Correct 130 ms 73148 KB Output is correct
26 Correct 126 ms 73428 KB Output is correct
27 Correct 257 ms 115184 KB Output is correct
28 Correct 266 ms 116676 KB Output is correct
29 Correct 33 ms 66248 KB Output is correct
30 Correct 33 ms 66260 KB Output is correct
31 Correct 33 ms 66312 KB Output is correct
32 Correct 34 ms 66224 KB Output is correct
33 Correct 357 ms 121292 KB Output is correct
34 Correct 509 ms 124408 KB Output is correct
35 Correct 614 ms 126944 KB Output is correct
36 Correct 821 ms 130352 KB Output is correct
37 Correct 282 ms 81328 KB Output is correct
38 Correct 280 ms 82464 KB Output is correct
39 Correct 290 ms 81236 KB Output is correct
40 Correct 296 ms 82500 KB Output is correct
41 Correct 289 ms 81200 KB Output is correct
42 Correct 297 ms 82444 KB Output is correct
43 Correct 249 ms 115148 KB Output is correct
44 Correct 255 ms 116512 KB Output is correct
45 Correct 139 ms 74864 KB Output is correct
46 Correct 168 ms 75396 KB Output is correct
47 Correct 351 ms 91784 KB Output is correct
48 Correct 592 ms 127880 KB Output is correct
49 Correct 122 ms 73676 KB Output is correct
50 Correct 122 ms 73640 KB Output is correct
51 Correct 121 ms 73848 KB Output is correct
52 Correct 127 ms 74216 KB Output is correct
53 Correct 126 ms 74328 KB Output is correct
54 Correct 126 ms 74220 KB Output is correct