oj.uz

Submission #555415

# Submission time Handle Problem Language Result Execution time Memory
555415 2022-04-30T21:25:25 Z shahriarkhan Street Lamps (APIO19_street_lamps) C++14
100 / 100
 2182 ms 103112 KB 
#include<bits/stdc++.h>
using namespace std ;

//T1 handles sums
//T2 handles, if it has already started or not!

const int N = 3e5 + 5 ;

int ans[N] , type[N] , stat[N] , signs[2] = {1,-1} ;

struct box
{
    int l = 0 , r = 0 , sign = 0 , val = 0 , val2 = 0 , idx = 0 , type = 0 ;
};

bool cmp1(box &a , box &b)
{
    if(a.l!=b.l) return a.l < b.l ;
    return a.type < b.type ;
}

bool cmp2(box &a , box &b)
{
    if(a.r!=b.r) return a.r < b.r ;
    return a.type < b.type ;
}

set<pair<int,int> > S ;

vector<box> v ;

void toggle(int l , int r , int i , int idx , int s)
{
    v.push_back({l,i,signs[s],idx,signs[s^1],idx,1}) ;
    v.push_back({l,r+1,signs[s^1],idx,signs[s],idx,1}) ;
    v.push_back({i+1,i,signs[s^1],idx,signs[s],idx,1}) ;
    v.push_back({i+1,r+1,signs[s],idx,signs[s^1],idx,1}) ;
}

void query(int l , int r , int idx)
{
    v.push_back({l,r-1,1,0,0,idx,2}) ;
}

struct BIT
{
	int bit[N] = {};
	void update(int p,int v) {
	    ++p ;
		for(;p< N; p+= p&-p) bit[p] += v;
	}
    int query(int p) {
        ++p ;
    	int r=0;
    	for(;p>0;p-=p&-p) r += bit[p];
        return r;
    }
    int query(int a,int b) {
    	return query(b) - query(a - 1);
    }
} T1 , T2;

void divide(int low , int high)
{
    if(low==high) return ;
    int mid = (low+high)>>1 ;
    divide(low,mid) , divide(mid+1,high) ;
    vector<int> rem ;
    vector<box> left , right ;
    for(int i = low ; i <= high ; ++i)
    {
        if(i<=mid)
        {
            if(v[i].type==1) left.push_back(v[i]) ;
        }
        else
        {
            if(v[i].type==2) right.push_back(v[i]) ;
        }
    }
    if(left.empty() || right.empty()) return ;
    sort(left.begin(),left.end(),cmp2) ;
    sort(right.begin(),right.end(),cmp2) ;
    int siz_left = left.size() , siz_right = right.size() , cur = 0 ;
    for(int i = 0 ; i < siz_right ; ++i)
    {
        while((cur<siz_left) && (left[cur].r<=right[i].r))
        {
            T1.update(left[cur].idx,left[cur].sign*left[cur].val) ;
            T2.update(left[cur].idx,left[cur].val2) ;
            //cout<<"left:"<<' '<<left[cur].l<<' '<<left[cur].r<<' '<<left[cur].idx<<endl ;
            rem.push_back(cur) ;
            ++cur ;
        }
        //cout<<"right:"<<' '<<right[i].l<<' '<<right[i].r<<' '<<right[i].idx<<' '<<T1.query(1,0,N,0,right[i].idx)<<' '<<T2.query(1,0,N,0,right[i].idx)<<endl ;
        ans[right[i].idx] += (right[i].sign*(T1.query(right[i].idx) + ((T2.query(right[i].idx)*right[i].idx)))) ;
    }
    for(int i : rem)
    {
        T1.update(left[i].idx,-(left[i].sign*left[i].val)) ;
        T2.update(left[i].idx,-left[i].val2) ;
    }
    return ;
}

int main()
{
    int n , q , t_l = -1 ;
    scanf("%d%d",&n,&q) ;
    string s ;
    cin>>s ;
    for(int i = 0 ; i < n ; ++i)
    {
        if(s[i]=='0')
        {
            stat[i+1] = 0 ;
            if(t_l>=0) S.insert({t_l+1,i}) , t_l = -1 ;
        }
        else
        {
            stat[i+1] = 1 ;
            if(t_l==(-1)) t_l = i ;
        }
    }
    if(t_l!=(-1)) S.insert({t_l+1,n}) ;
    for(pair<int,int> p : S)
    {
        int l = p.first , r = p.second ;
        v.push_back({l,0,1,0,1,0,1}) ;
        v.push_back({l,r+1,-1,0,-1,0,1}) ;
        v.push_back({r+1,0,-1,0,-1,0,1}) ;
        v.push_back({r+1,r+1,1,0,1,0,1}) ;
    }
    for(int time = 1 ; time <= q ; ++time)
    {
        string t ;
        cin>>t ;
        if(t=="toggle")
        {
            type[time] = 1 ;
            int idx ;
            scanf("%d",&idx) ;
            stat[idx] ^= 1 ;
            int l = 0 , r = 0 ;
            vector<pair<int,int> > rem ;
            if(stat[idx])
            {
                auto it2 = S.lower_bound({idx+1,0}) ;
                if(it2!=S.end())
                {
                    pair<int,int> cur = *it2 ;
                    if(cur.first==(idx+1))
                    {
                        rem.push_back(cur) ;
                        r = cur.second ;
                    }
                    else r = idx ;
                }
                else r = idx ;
                if(it2!=S.begin())
                {
                    pair<int,int> cur = *(--it2) ;
                    if(cur.second==(idx-1))
                    {
                        rem.push_back(cur) ;
                        l = cur.first ;
                    }
                    else l = idx ;
                }
                else l = idx ;
                for(pair<int,int> p : rem)
                {
                    S.erase(p) ;
                }
                S.insert({l,r}) ;
            }
            else
            {
                auto it = --S.lower_bound({idx+1,0}) ;
                pair<int,int> cur = *it ;
                l = cur.first , r = cur.second ;
                rem.push_back(cur) ;
                for(pair<int,int> p : rem)
                {
                    S.erase(p) ;
                }
                if(l<=(idx-1)) S.insert({l,idx-1}) ;
                if((idx+1)<=r) S.insert({idx+1,r}) ;
            }
            toggle(l,r,idx,time,stat[idx]) ;
        }
        else
        {
            type[time] = 2 ;
            int a , b ;
            scanf("%d%d",&a,&b) ;
            query(a,b,time) ;
        }
    }
    int siz = v.size() ;
    sort(v.begin(),v.end(),cmp1) ;
    divide(0,siz-1) ;
    for(int i = 1 ; i <= q ; ++i)
    {
        if(type[i]==2) printf("%d\n",ans[i]) ;
    }
    return 0 ;
}

Compilation message

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:109:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |     scanf("%d%d",&n,&q) ;
      |     ~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:142:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |             scanf("%d",&idx) ;
      |             ~~~~~^~~~~~~~~~~
street_lamps.cpp:196:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  196 |             scanf("%d%d",&a,&b) ;
      |             ~~~~~^~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 739 ms 48252 KB Output is correct
2 Correct 826 ms 48080 KB Output is correct
3 Correct 1040 ms 48600 KB Output is correct
4 Correct 1865 ms 66164 KB Output is correct
5 Correct 1709 ms 59988 KB Output is correct
6 Correct 2029 ms 68568 KB Output is correct
7 Correct 245 ms 28328 KB Output is correct
8 Correct 282 ms 29664 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 5 ms 596 KB Output is correct
3 Correct 5 ms 596 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1689 ms 86000 KB Output is correct
6 Correct 2081 ms 84344 KB Output is correct
7 Correct 1715 ms 63568 KB Output is correct
8 Correct 289 ms 29668 KB Output is correct
9 Correct 229 ms 19640 KB Output is correct
10 Correct 276 ms 25120 KB Output is correct
11 Correct 249 ms 24476 KB Output is correct
12 Correct 244 ms 28436 KB Output is correct
13 Correct 288 ms 29784 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 4 ms 596 KB Output is correct
3 Correct 4 ms 596 KB Output is correct
4 Correct 5 ms 704 KB Output is correct
5 Correct 1120 ms 35436 KB Output is correct
6 Correct 1590 ms 54392 KB Output is correct
7 Correct 2052 ms 67448 KB Output is correct
8 Correct 2182 ms 103112 KB Output is correct
9 Correct 1094 ms 59148 KB Output is correct
10 Correct 1172 ms 84108 KB Output is correct
11 Correct 1088 ms 59136 KB Output is correct
12 Correct 1153 ms 84200 KB Output is correct
13 Correct 1082 ms 59216 KB Output is correct
14 Correct 1165 ms 84068 KB Output is correct
15 Correct 239 ms 28352 KB Output is correct
16 Correct 288 ms 29636 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 739 ms 48252 KB Output is correct
9 Correct 826 ms 48080 KB Output is correct
10 Correct 1040 ms 48600 KB Output is correct
11 Correct 1865 ms 66164 KB Output is correct
12 Correct 1709 ms 59988 KB Output is correct
13 Correct 2029 ms 68568 KB Output is correct
14 Correct 245 ms 28328 KB Output is correct
15 Correct 282 ms 29664 KB Output is correct
16 Correct 2 ms 596 KB Output is correct
17 Correct 5 ms 596 KB Output is correct
18 Correct 5 ms 596 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1689 ms 86000 KB Output is correct
21 Correct 2081 ms 84344 KB Output is correct
22 Correct 1715 ms 63568 KB Output is correct
23 Correct 289 ms 29668 KB Output is correct
24 Correct 229 ms 19640 KB Output is correct
25 Correct 276 ms 25120 KB Output is correct
26 Correct 249 ms 24476 KB Output is correct
27 Correct 244 ms 28436 KB Output is correct
28 Correct 288 ms 29784 KB Output is correct
29 Correct 2 ms 468 KB Output is correct
30 Correct 4 ms 596 KB Output is correct
31 Correct 4 ms 596 KB Output is correct
32 Correct 5 ms 704 KB Output is correct
33 Correct 1120 ms 35436 KB Output is correct
34 Correct 1590 ms 54392 KB Output is correct
35 Correct 2052 ms 67448 KB Output is correct
36 Correct 2182 ms 103112 KB Output is correct
37 Correct 1094 ms 59148 KB Output is correct
38 Correct 1172 ms 84108 KB Output is correct
39 Correct 1088 ms 59136 KB Output is correct
40 Correct 1153 ms 84200 KB Output is correct
41 Correct 1082 ms 59216 KB Output is correct
42 Correct 1165 ms 84068 KB Output is correct
43 Correct 239 ms 28352 KB Output is correct
44 Correct 288 ms 29636 KB Output is correct
45 Correct 389 ms 31456 KB Output is correct
46 Correct 509 ms 31348 KB Output is correct
47 Correct 1035 ms 38392 KB Output is correct
48 Correct 1931 ms 69952 KB Output is correct
49 Correct 296 ms 27048 KB Output is correct
50 Correct 300 ms 27416 KB Output is correct
51 Correct 295 ms 26724 KB Output is correct
52 Correct 323 ms 26284 KB Output is correct
53 Correct 321 ms 26208 KB Output is correct
54 Correct 327 ms 26176 KB Output is correct