Submission #1045022

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045022		NotLinux	Street Lamps (APIO19_street_lamps)	C++17	0 / 100	288 ms	334340 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
const int N = 3e5 + 7;
const int inf = 1e9 + 7;
struct PersistentLazySegt{
	struct Node{
		int left , right , mn , mncnt , lzt;
		Node(int x):left(-1) , right(-1) , mn(x) , mncnt(1) , lzt(0){}
	};
	vector < Node > tree;
	vector < int > roots;
	Node merge(int a , int b){
		// cout << "MERGE ----" << endl;
		// cout << "a : " << tree[a].mn << " " << tree[a].mncnt << endl;
		// cout << "b : " << tree[b].mn << " " << tree[b].mncnt << endl;
		Node c(inf);
		c.left = a;
		c.right = b;
		c.mn = min(tree[a].mn , tree[b].mn);
		c.mncnt = 0;
		// cout << "c : " << c.mn << " " << c.mncnt << endl;
		if(tree[a].mn == c.mn)c.mncnt += tree[a].mncnt;
		// cout << "c : " << c.mn << " " << c.mncnt << endl;
		if(tree[b].mn == c.mn)c.mncnt += tree[b].mncnt;
		// cout << "c : " << c.mn << " " << c.mncnt << endl;
		// cout << "WTF : " << tree[a].mn << " == " << c.mn << endl;
		// cout << "WTF : " << tree[b].mn << " == " << c.mn << endl;
		// cout << "----" << endl;
		return c;
	}
	pair < int , int > merge(pair < int , int > a , pair < int , int > b){
		if(a.first == b.first){
			a.second += b.second;
			return a;
		}
		else{
			if(a.first < b.first)return a;
			else return b;
		}
	}
	int build(int l , int r){
		if(l == r){
			tree.push_back(Node(0));
			// cout << l << " " << r << " : " << tree[sz(tree) - 1].mn << " " << tree[sz(tree) - 1].mncnt << " " << tree[sz(tree) - 1].lzt << endl;
			return sz(tree) - 1;
		}
		tree.push_back(Node(0));
		int mid = (l + r) >> 1 , myind = sz(tree) - 1;
		tree[myind] = merge(build(l , mid) , build(mid+1 , r));
		// cout << l << " " << r << " : " << tree[myind].mn << " " << tree[myind].mncnt << " " << tree[myind].lzt << endl;
		return myind;
	}
	void init(){
		roots.push_back(build(1 , N));
	}
	void push(int ind , int l , int r){
		if(tree[ind].lzt){
			tree[ind].mn += tree[ind].lzt;
			int mid = (l + r) / 2;
			// cout << "push : " << ind << " " << l << " " << r << " : " << tree[ind].mn << " , " << tree[ind].lzt << endl;
			// cout << "pushkids : " << tree[ind].left << " , " << tree[ind].right << endl;
			if(l != r){
				// cout << "nice" << endl;
				// left kid
				// cout << "left : " << tree[tree[ind].left].mn << " " << tree[ind].left << endl;
				tree.push_back(tree[tree[ind].left]);
				tree[sz(tree) - 1].lzt += 1;
				tree[ind].left = sz(tree) - 1;
				// cout << "left : " << tree[tree[ind].left].mn << " " << tree[tree[ind].left].mncnt << endl;
				// right kid
				tree.push_back(tree[tree[ind].right]);
				tree[sz(tree) - 1].lzt += 1;
				tree[ind].right = sz(tree) - 1;
				// cout << "right : " << tree[tree[ind].right].mn << " " << tree[tree[ind].right].mncnt << endl;
			}
			// cout << "pushkids1 : " << tree[ind].left << " , " << tree[ind].right << endl;
			tree[ind].lzt = 0;
		}
	}
	pair < int , int > query(int ql , int qr , int ind = 0 , int l = 1 , int r = N){
		push(ind,l,r);
		// cout << "\nQUERY : " << ind << " " << l << " " << r << " : " << tree[ind].mn << " " << tree[ind].mncnt << endl;
		if(l >= ql and r <= qr){
			return {tree[ind].mn , tree[ind].mncnt};
		}
		else if(l > qr or r < ql){
			return {inf , 0};
		}
		else{
			int mid = (l + r) >> 1;
			return merge(query(ql , qr , tree[ind].left , l , mid) , query(ql , qr , tree[ind].right , mid+1 , r));
		}
	}
	int update(int ql , int qr , int ind = 0 , int l = 1 , int r = N){
		push(ind,l,r);
		if(l >= ql and r <= qr){
			tree.push_back(tree[ind]);
			int myind = sz(tree) - 1;
			tree[myind].lzt += 1;
			push(myind,l,r);
			// cout << myind << " update1 : " << l << " " << r << " = " << tree[myind].mn << " , " << tree[myind].mncnt << endl;
			return myind;
		}
		else{
			int mid = (l + r) >> 1;
			Node thisnode = tree[ind];
			if((l > qr or mid < ql) == 0){
				thisnode.left = update(ql , qr , tree[ind].left , l , mid);
			}
			if((mid+1 > qr or r < ql) == 0){
				thisnode.right = update(ql , qr , tree[ind].right , mid+1 , r);
			}
			thisnode = merge(thisnode.left , thisnode.right);
			tree.push_back(thisnode);
			// cout << sz(tree)-1 << " update2 : " << l << " " << r << " = " << thisnode.mn << " , " << thisnode.mncnt << endl;
			// cout << "kids : " << thisnode.left << " " << thisnode.right << endl;
			// cout << "left : " << tree[thisnode.left].mn << " " << tree[thisnode.left].mncnt << endl;
			// cout << "right : " << tree[thisnode.right].mn << " " << tree[thisnode.right].mncnt << endl;
			return sz(tree) - 1;
		}
	}
	void new_update(int l , int r){
		roots.push_back(update(l , r , roots.back()));
	}
} pst;
void solve(){
	// const int n = 20;
	// pst.init();
	// while(true){
	// 	int typ;
	// 	cin >> typ;
	// 	if(typ == 1){
	// 		int l,r;
	// 		cin >> l >> r;
	// 		pst.new_update(l ,r);
	// 	}
	// 	else if(typ == 2){
	// 		int k;
	// 		cin >> k;
	// 		for(int i = 1;i<=n;i++)cout << pst.query(i,i,pst.roots[k]).first << " ";cout << endl;
	// 	}
	// 	else{
	// 		int k,l,r;
	// 		cin >> k >> l >> r;
	// 		cout << "res : " << pst.query(l,r,pst.roots[k]).first << " , " << pst.query(l,r,pst.roots[k]).second << endl;
	// 	}
	// 	for(int i = 1;i<=n;i++)cout << pst.query(i,i,pst.roots[sz(pst.roots) - 1]).first << " ";cout << endl;
	// }
	// N = 100
	pst.init();
	int n,q;
	cin >> n >> q;
	string str;
	cin >> str;

	for(int i = 0;i<sz(str);i++){
		if(str[i] == '0')str[i] = '1';
		else str[i] = '0';
	}

	vector < pair < int , int > > ranges[n+1];
	int version_map[n+2] , last[n+1];
	memset(version_map , -1 , sizeof(version_map));
	version_map[0] = 0;
	memset(last , -1 , sizeof(last));
	for(int i = 0;i<n;i++){
		if(str[i] == '1')last[i+1] = 1;
	}
	// cout << "flag0" << endl;
	vector < array < int , 3 > > queries;
	for(int t = 2;t<=q+1;t++){
		string typ;
		cin >> typ;
		if(typ == "toggle"){
			int x;
			cin >> x;
			if(last[x] == -1)last[x] = t;
			else {
				ranges[x].push_back({last[x] , t-1});
				last[x] = -1;
			}
		}
		else{
			int l,r;
			cin >> l >> r;
			queries.push_back({l , r , t-1});
		}
	}
	// cout << "flag1" << endl;
	for(int i = 1;i<=n;i++){
		if(last[i] != -1){
			ranges[i].push_back({last[i] , q+1});
		}
	}
	// cout << "flag2" << endl;
	for(int i = 1;i<=n;i++){
		for(auto itr : ranges[i]){
			// cout << "flag2.5" << endl;
			pst.new_update(itr.first , itr.second);
			// cout << i << " new update : " << itr.first << " , " << itr.second  << endl;
		}
		// cout << "last : ";for(int j = 1;j<=q+1;j++)cout << pst.query(j , j , pst.roots.back()).first << " ";cout << endl;
		version_map[i] = pst.roots.back();
	}
	version_map[n+1] = pst.roots.back();
	// cout << "###########" << endl;
	// for(int i = 1;i<=n;i++){
	// 	cout << i << " : ";for(int j = 1;j<=q+1;j++)cout << pst.query(j , j , version_map[i]).first << " ";cout << endl;
	// }
	// cout << "flag3" << endl;
	for(auto itr : queries){
		// cout << "query : " << itr[0] << " " << itr[1] << " " << itr[2] << endl;
		pair < int , int > r_val = pst.query(1 , itr[2] , version_map[itr[1]]);
		pair < int , int > l_val = pst.query(1 , itr[2] , version_map[itr[0]-1]);
		// cout << "lval : " << l_val.first << " " << l_val.second << endl;
		// cout << "rval : " << r_val.first << " " << r_val.second << endl;
		if(l_val.first == r_val.first){
			cout << r_val.second << '\n';
		}
		else {
			cout << 0 << '\n';
		}
	}
	// cout << "flag4" << endl;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase=1;//cin >> testcase;
	while(testcase--)solve();
	cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl;
}

Compilation message (stderr)

street_lamps.cpp: In member function 'void PersistentLazySegt::push(int, int, int)':
street_lamps.cpp:61:8: warning: unused variable 'mid' [-Wunused-variable]
   61 |    int mid = (l + r) / 2;
      |        ^~~

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