oj.uz

Submission #906695

# Submission time Handle Problem Language Result Execution time Memory
906695 2024-01-14T18:25:37 Z Itamar Street Lamps (APIO19_street_lamps) C++14
20 / 100
 846 ms 76264 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 14940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 315 ms 19120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14940 KB Output is correct
2 Correct 5 ms 14940 KB Output is correct
3 Correct 7 ms 14988 KB Output is correct
4 Correct 6 ms 14940 KB Output is correct
5 Correct 641 ms 74528 KB Output is correct
6 Correct 827 ms 75736 KB Output is correct
7 Correct 846 ms 76264 KB Output is correct
8 Correct 708 ms 44096 KB Output is correct
9 Correct 400 ms 18516 KB Output is correct
10 Correct 445 ms 18856 KB Output is correct
11 Correct 445 ms 19432 KB Output is correct
12 Correct 749 ms 41528 KB Output is correct
13 Correct 687 ms 44008 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14940 KB Output is correct
2 Incorrect 6 ms 14940 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 14940 KB Output isn't correct
2 Halted 0 ms 0 KB -