Submission #264565

#	Time	Username	Problem	Language	Result	Execution time	Memory
264565		dimash241	Street Lamps (APIO19_street_lamps)	C++17	0 / 100	3864 ms	198092 KiB

street_lamps

//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")

//# include <x86intrin.h>
# include <bits/stdc++.h>

# include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
 
template<typename T> using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define For(i,x,y)  for (ll i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (ll i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
// ROAD to...                                                                                                                                                                                                                Red

void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void setIO(string s = "") {
	// cin.exceptions(cin.failbit); 
	// throws exception when do smth illegal
	// ex. try to read letter into int
	if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}

const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9;
const int N = 3e5 + 3;                                          
const int M = 22;
const int pri = 997;
const int Magic = 2101;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
 
int rnd (int l, int r) {
	return uniform_int_distribution<int> (l, r)(gen);
}

set < array<int,3> > act;
//on segments l, r, st_time
int n, m;
string s;

int t[N*18*18];
int L[N*18*18];
int R[N*18*18];
int root[N];

int ptr;

void updQuery (int l, int r, int x, int &v, int tl = 1, int tr = N) {
	if (tl > r || l > tr || l > r) return;
	if (!v) v = ++ptr;
	if (l <= tl && tr <= r) {
		t[v] += x;
		return;
	}
	
	int tm = (tl+tr)>>1;
	updQuery(l, r, x, L[v], tl, tm);
	updQuery(l, r, x, R[v], tm+1, tr);
}

int getQuery (int p, int v, int tl = 1, int tr = N) {
	if (tl == tr || !v) {
		return t[v];
	}
	
	int tm = (tl+tr)>>1;
	
	if(p <= tm) return t[v] + getQuery(p, L[v], tl, tm);
	
	return t[v] + getQuery(p, R[v], tm+1, tr);
}

int getCalc (int v, int r) {
	int res = 0;
	while(v) {
		res += getQuery(r, root[v]);
		v -= (v&-v);
	}
	return res;
}

void updRec (int v, int l, int r, int x) {
	while(v < N) {
		updQuery(l, r, x, root[v]);
		v += (v&-v);
	}
}

void turn_off (int pos, int i) {
	auto cur = *prev(act.lb({pos+1, 0, 0}));
	
	updRec (cur[0], cur[0], cur[1], i-cur[2]);
	updRec (cur[1]+1, cur[0], cur[1], cur[2]-i);
	
	act.erase(cur);
	act.insert({cur[0], pos, i});
	act.insert({pos+1, cur[1], 1});
}

void turn_on (int pos, int i) {
	auto curL = *prev(act.lb({pos+1, 0, 0}));
	auto curR = *prev(act.lb({pos+2, 0, 0}));
	
	updRec (curL[0], curL[0], curL[1], i-curL[2]);
	updRec (curL[1]+1, curL[0], curL[1], curL[2]-i);
	updRec (curR[0], curR[0], curR[1], i-curR[2]);
	updRec (curR[1]+1, curR[0], curR[1], curR[2]-i);
	
	act.erase(curL);
	act.erase(curR);
	act.insert({curL[0], curR[1], i});
}

int main () {
	SpeedForce;
	
	cin >> n >> m >> s;
	s='0'+s;
	for (auto &e : s) e -= '0';
	
	for (int i = 1; i <= n; ++i) {
		{
			int j = i;
			while(j <= n && s[j]) ++j;
			act.insert({i, j, 0});
			i = j;
		}
	}
	
	for (int i = 1; i <= m; ++i) {
		string op;
		cin >> op;
		
		if (op[0] == 't') {
			int pos;
			cin >> pos;
			if(s[pos]) {
				turn_off(pos, i);
			} else {
				turn_on(pos, i);
			}
			
			s[pos] ^= 1;
		} else {
			int l, r;
			cin >> l >> r;
			//in rectangle x = {1, l} y = {1, r} 
			int ans = getCalc(l, r);
			auto cur = *prev(act.lb({l+1, 0, 0}));
			if (cur[1] >= r) ans += i-cur[2];
			
			cout << ans << '\n';
		}
	}
	
	
	return Accepted;
}

// B...a

Compilation message (stderr)

street_lamps.cpp: In function 'void setIn(std::string)':
street_lamps.cpp:34:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   34 | void setIn(string s) { freopen(s.c_str(),"r",stdin); }
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp: In function 'void setOut(std::string)':
street_lamps.cpp:35:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   35 | void setOut(string s) { freopen(s.c_str(),"w",stdout); }
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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