이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 MX , 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.r < b.r ;
}
bool cmp2(box &a , box &b)
{
if(a.r!=b.r) return a.r < b.r ;
return a.idx < b.idx ;
}
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 tree
{
vector<int> T ;
void init(int n)
{
T = vector<int> (4*n + 4 , 0) ;
}
void update(int node , int low , int high , int idx , int val)
{
if((idx<low) || (high<idx)) return ;
if(low==high)
{
T[node] += val ;
return ;
}
int mid = (low+high)>>1 , left = node<<1 , right = left|1 ;
update(left,low,mid,idx,val) ;
update(right,mid+1,high,idx,val) ;
T[node] = T[left] + T[right] ;
}
int query(int node , int low , int high , int l , int r)
{
if(l>r) return 0 ;
if((r<low) || (l>high)) return 0 ;
if((l<=low) && (high<=r)) return T[node] ;
int mid = (low+high)>>1 , left = node<<1 , right = left|1 ;
return (query(left,low,mid,l,r)+query(right,mid+1,high,l,r)) ;
}
} 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(1,0,N,left[cur].idx,left[cur].sign*left[cur].val) ;
T2.update(1,0,N,left[cur].idx,left[cur].val2) ;
rem.push_back(cur) ;
++cur ;
}
ans[right[i].idx] += (right[i].sign*(T1.query(1,0,N,0,right[i].idx) + ((T2.query(1,0,N,0,right[i].idx)*right[i].idx)))) ;
}
for(int i : rem)
{
T1.update(1,0,N,left[i].idx,-(left[i].sign*left[i].val)) ;
T2.update(1,0,N,left[i].idx,-left[i].val2) ;
}
return ;
}
int main()
{
int n , q , t_l = -1 ;
scanf("%d%d",&n,&q) ;
MX = n + 5 ;
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({MX+1,0,-1,0,-1,0,1}) ;
v.push_back({MX+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!=r) S.insert({l,idx-1}) , 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) ;
T1.init(N) , T2.init(N) ;
divide(0,siz-1) ;
for(int i = 1 ; i <= q ; ++i)
{
if(type[i]==2) printf("%d\n",ans[i]) ;
}
return 0 ;
}
컴파일 시 표준 에러 (stderr) 메시지
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:119:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
119 | scanf("%d%d",&n,&q) ;
| ~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:153:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
153 | scanf("%d",&idx) ;
| ~~~~~^~~~~~~~~~~
street_lamps.cpp:206:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
206 | scanf("%d%d",&a,&b) ;
| ~~~~~^~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |