# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
140572 | luciocf | 가로등 (APIO19_street_lamps) | C++14 | 5096 ms | 16916 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int maxn = 3e5+10;
struct Op
{
int type;
int ind;
} query[maxn];
struct E
{
int type;
int l, r;
} event[maxn];
int n, q;
int last[maxn];
int ans[maxn];
int pai[maxn], peso[maxn];
int edge[maxn], nivel[maxn];
bool on[maxn];
bool mark[maxn];
void init(void)
{
for (int i = 1; i <= n+1; i++)
pai[i] = i, peso[i] = 1;
}
int Find(int x)
{
if (pai[x] == x) return x;
return Find(pai[x]);
}
void Join(int x, int y, int t)
{
x = Find(x), y = Find(y);
if (x == y) return;
if (peso[x] < peso[y]) swap(x, y);
pai[y] = x, peso[x] += peso[y];
edge[y] = t;
}
int dfs(int u, int p)
{
if (u == p) return 0;
return nivel[u] = dfs(pai[u], p)+1;
}
int lca(int u, int v)
{
int ans = 0;
while (u != v)
{
if (nivel[u] > nivel[v]) ans = max(ans, edge[u]), u = pai[u];
else ans = max(ans, edge[v]), v = pai[v];
}
return ans;
}
void solve_small(void)
{
for (int i = 1; i <= q; i++)
{
string op;
cin >> op;
if (op == "toggle")
{
int ind;
scanf("%d", &ind);
query[i] = {0, ind};
}
else
{
int l, r;
scanf("%d %d", &l, &r);
query[i] = {1, -1};
int ans = 0;
for (int j = 1; j <= n; j++)
mark[j] = on[j];
for (int j = 1; j <= i; j++)
{
if (query[j].type == 1)
{
bool ok = 1;
for (int k = l; k < r; k++)
if (!mark[k])
ok = 0;
if (ok) ans++;
}
else
{
bool ok = 1;
for (int k = l; k < r; k++)
if (!mark[k])
ok = 0;
if (ok) ans++;
mark[query[j].ind] = !mark[query[j].ind];
}
}
printf("%d\n", ans);
}
}
}
void solve_two(void)
{
for (int i = 1; i <= q; i++)
{
if (event[i].type == 0)
{
int ind = event[i].l;
on[ind] = !on[ind];
if (!on[ind])
ans[ind] += (i-last[ind]);
last[ind] = i;
}
else
{
int l = event[i].l, r = event[i].r;
int tot = ans[l];
if (on[l]) tot += (i-last[l]);
printf("%d\n", tot);
}
}
}
int main(void)
{
scanf("%d %d", &n, &q);
init();
for (int i = 1; i <= n; i++)
{
char x;
scanf(" %c", &x);
if (x == '1')
{
on[i] = true;
Join(i, i+1, 0);
}
}
if (n <= 100 && q <= 100)
{
solve_small();
return 0;
}
bool ok = 1;
for (int i = 1; i <= q; i++)
{
string s;
cin >> s;
if (s == "toggle")
{
int ind;
scanf("%d", &ind);
event[i] = {0, ind, -1};
Join(ind, ind+1, i);
}
else
{
int l, r;
scanf("%d %d", &l, &r);
event[i] = {1, l, r};
if (r != l+1) ok = 0;
}
}
if (ok)
{
solve_two();
return 0;
}
for (int i = 1; i <= n; i++)
dfs(i, Find(i));
for (int i = 1; i <= q; i++)
{
if (event[i].type)
{
int l = event[i].l, r = event[i].r;
int first = lca(l, r);
if (first > i || Find(l) != Find(r)) printf("0\n");
else printf("%d\n", i-first);
}
}
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |