Submission #437558

#	Time	Username	Problem	Language	Result	Execution time	Memory
437558		RohamIzadidoost	Street Lamps (APIO19_street_lamps)	C++17	60 / 100	4448 ms	524292 KiB

street_lamps

#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define pll pair<ll , ll >
#define all(x) (x).begin(),(x).end()
#define SZ(x) (ll)(x).size()
#define X   first
#define Y   second
#define mp  make_pair
#define pii pair<int , int>
#define vec vector
#define file_io freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define ld long double
// BIG p : 1000000000000037 , 100000000003
ll poww(ll a, ll b, ll md) {
    return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}
const int maxn = 3000*100+5 ;
const ll inf = 9223372036854775807 ;
const ll mod = 1e9 + 7 ;
const int lg = 20 ;
int n , q ; 
string c ; 
set<int> s ; 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
gp_hash_table<int, ll> fen[maxn];
ll res ;  
inline void add(int l , int r , ll x){
	for( ; l < maxn ; l += l & -l ) for(int i = r ; i < maxn ; i += i & -i ) fen[l][i] += x ; 
}
inline void get(int l , int r){
	res = 0 ; 
	for( ; l ; l &= l-1 ) for(int i = r ; i ; i &= i-1) if(fen[l].find(i) != fen[l].end()) res += fen[l][i] ; 
}
void doj(int l , int r , int l2 , int r2 , ll x){
	add(l , r , x) ; 
	add(l2 + 1 , r2 + 1 , x) ; 
	add(l , r2 + 1 , -x) ; 
	add(l2 + 1 , r , -x) ; 
}
int main()
{
	migmig ;
	/*for(int i = 1 ; i < maxn ; i ++ ){
		fen[i].max_load_factor(0.13); 
	}*/
	cin>>n>>q>>c ; 
	s.insert(0) ;
	s.insert(n + 1) ;  
	for(int i = 0 ; i < n ; i ++ ){
		if(c[i] == '0') s.insert(i + 1) ; 
	}
	ll l , r ;
	ll v ;  
	for(ll i = 1 ; i <= q ; i ++ ){
		cin>>c ; 
		if(c == "query"){
			cin>>l>>r ; 
			get(l , r) ; 
			//cout<<*s.lower_bound(l) << endl ; 
			if(s.lower_bound(l) == s.lower_bound(r) ) res += i ; 
			cout<<res << "\n" ; 
			continue ; 	
		}
		cin>>v ; 
		auto p = s.lower_bound(v) ; 
		if(*p == v){
			l = *prev(p) + 1 ; 
			r = *next(p) ; 
			s.erase(v) ; 
			doj(l , v + 1 , v , r , -i ) ;
		//	cout<<l <<","<< r << endl ; 
			continue ;  
		}
		l = *prev(p) + 1 ; 
		r = *p ; 
	//	cout<<l<<" " << r << endl ; 
		s.insert(v) ; 
		doj(l , v + 1 , v , r , i) ; 
	}
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 20 / 20
• Subtask 5: 0 / 20