Submission #983738

#	Time	Username	Problem	Language	Result	Execution time	Memory
983738		pcc	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	297 ms	53440 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define fs first
#define sc second

const int mxn = 3e5+10;
int N,Q;
int arr[mxn];
pii tree[mxn];

pii req[mxn];

namespace TREE{
	int par[mxn][20];
	int dep[mxn];
	vector<int> st;
	void dfs(int now){
		for(int i = 1;i<20;i++){
			par[now][i] = par[par[now][i-1]][i-1];
		}
		if(tree[now].fs){
			par[tree[now].fs][0] = now;
			dep[tree[now].fs] = dep[now]+1;
			dfs(tree[now].fs);
		}
		if(tree[now].sc){
			par[tree[now].sc][0] = now;
			dep[tree[now].sc] = dep[now]+1;
			dfs(tree[now].sc);
		}
		return;
	}
	void BUILD(){
		for(int i = 1;i<=N;i++){
			while(!st.empty()&&arr[st.back()]<=arr[i]){
				tree[i].fs = st.back();
				st.pop_back();
			}
			if(!st.empty()){
				tree[st.back()].sc = i;
			}
			st.push_back(i);
		}
		par[st[0]][0] = st[0];
		dfs(st[0]);
	}
	int LCA(int a,int b){
		if(dep[a]<dep[b])swap(a,b);
		int d = dep[a]-dep[b];
		for(int i = 19;i>=0;i--){
			if(d&(1<<i))a = par[a][i];
		}
		for(int i = 19;i>=0;i--){
			if(par[a][i] != par[b][i])a = par[a][i],b = par[b][i];
		}
		return a== b?a:par[a][0];
	}
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>Q;
	if(N>mxn||Q>mxn)return 0;
	string s;
	cin>>s;
	s = "#"+s;
	fill(arr,arr+mxn,mxn);
	for(int i = 1;i<=N;i++){
		if(s[i] == '1')arr[i] = 0;
	}
	for(int i = 1;i<=Q;i++){
		string t;
		cin>>t;
		if(t[0] == 'q'){
			cin>>req[i].fs>>req[i].sc;
		}
		else{
			req[i].fs = 0;
			cin>>req[i].sc;
			arr[req[i].sc] = i;
		}
	}
	TREE::BUILD();
	for(int i = 1;i<=Q;i++){
		if(req[i].fs){
			int p = TREE::LCA(req[i].fs,req[i].sc-1);
			cout<<max(0,i-arr[p])<<'\n';
		}
	}
	return 0;
}

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