| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 914470 | ALTAKEXE | 디지털 회로 (IOI22_circuit) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "circuit.h"
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
const ll MOD = 1000002022;
ll n, m;
ll p[1000001], sz[1000001], v[100001], d1[200001], d2[200001];
bool lz[2000001];
vector<ll> d[100001];
void dfs(ll u)
{
for (auto v : d[u])
{
sz[v] = sz[u] + 1;
dfs(v);
}
}
void build(ll l, ll r, ll i, vector<ll> &t)
{
if (l == r)
{
if (t[l])
{
d1[i] = v[l];
}
else
{
d2[i] = v[l];
}
return;
}
ll md = (l + r) / 2;
build(l, md, 2 * i, t);
build(md + 1, r, 2 * i + 1, t);
d1[i] = (d1[2 * i] + d1[2 * i + 1]) % MOD;
d2[i] = (d2[2 * i] + d2[2 * i + 1]) % MOD;
}
void lazy(ll l, ll r, ll i)
{
if (!lz[i])
return;
lz[i] = 0;
swap(d1[i], d2[i]);
if (l == r)
return;
lz[2 * i] = !lz[2 * i];
lz[2 * i + 1] = !lz[2 * i + 1];
}
void update(ll l, ll r, ll i, ll ql, ll qr)
{
lazy(l, r, i);
if (r < ql || qr < l)
return;
if (ql <= l && r <= qr)
{
lz[i] = 1;
lazy(l, r, i);
return;
}
ll md = (l + r) / 2;
update(l, md, 2 * i, ql, qr);
update(md + 1, r, 2 * i + 1, ql, qr);
d1[i] = (d1[2 * i] + d1[2 * i + 1]) % MOD;
d2[i] = (d2[2 * i] + d2[2 * i + 1]) % MOD;
}
void init(ll N, ll M, vector<ll> P, vector<ll> A)
{
p[0] = 1;
n = N;
m = M;
for (ll i = 1; i < N + M; i++)
p[i] = (p[i - 1] * 2) % MOD;
for (ll i = 1; i < N + M; i++)
d[P[i]].push_back(i);
dfs(0);
for (ll i = N; i < N + M; i++)
v[i - N] = p[N - sz[i]];
build(0, M - 1, 1, A);
}
ll count_ways(ll L, ll R)
{
update(0, m - 1, 1, L - n, R - n);
return d1[1];
}