Submission #906695

#	Time	Username	Problem	Language	Result	Execution time	Memory
906695		Itamar	Street Lamps (APIO19_street_lamps)	C++14	20 / 100	846 ms	76264 KiB

street_lamps

#include <iostream>
using namespace std;
#include <vector>
#define vi vector<int>
#define ll long long
#include <algorithm>
#include <set>
#include <string>
#include <bitset>
#include <cmath>
#include <math.h>
#define pll pair<ll,ll>
#define vll vector<ll>
#define pi pair<int,int>
#include <map>
#include <queue>
#define x first
#define y second
#define pd pair<double,double>

const int siz = 3e5 + 1;
int my[siz];
vi c[siz];
vector<pi> his[siz];
void con(int a, int b, int i) {
	int u = my[a], v = my[b];
	if (u == v)return;
	if (c[u].size() > c[v].size())swap(u, v);
	for (int t : c[u]) {
		my[t] = v;
		c[v].push_back(t);
		his[t].push_back({ i,v });
	}
}
int main()
{
	int n, q;
	cin >> n >> q;
	vector<bool> s(n);
	string stt; cin >> stt;
	for (int i = 0; i < n; i++) {
		char c=stt[i]; if (c == '1')s[i] = 1;
	}
	for (int i = 0; i <= n; i++) {
		his[i].push_back({ -1, i }); my[i] = i; c[i].push_back(i);
	}
	for (int j = 0; j < n; j++) {
		int i = -1;
		if (s[j])con(j + 1, j, i);
	}
	for (int i = 0; i < q; i++) {
		string st; cin >> st;
		if (st == "toggle") {
			int j;
			cin >> j;
			j--;
			con(j, j + 1,i);
		}
		else {
			int a, b;
			cin >> a >> b;
			a--, b--;
			int ans = 0;
			for (pi p1 : his[a]) {
				for (pi p2 : his[b]) {
					if (p1.y == p2.y) {
						ans = max(ans, i - max(p1.x, p2.x));
					}
				}
			}
			cout << ans << "\n";
		}
	}
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file

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