| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 102788 | njchung99 | 즐거운 사진 수집 (JOI13_collecting) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
ll seg[1 << 22];
ll seg1[1 << 22];
ll cc[1 << 20 + 1];
ll cc1[1 << 20 + 1];
ll n, m;
ll check[22];
ll update(ll pos, ll val, ll node, ll x, ll y)
{
if (pos < x || y < pos)return seg[node];
if (x == y)return seg[node] = val;
ll mid = (x + y) / 2;
return seg[node] = update(pos, val, node * 2, x, mid) + update(pos, val, node * 2 + 1, mid + 1, y);
}
ll update1(ll pos, ll val, ll node, ll x, ll y)
{
if (pos < x || y < pos)return seg1[node];
if (x == y)return seg1[node] = val;
ll mid = (x + y) / 2;
return seg1[node] = update1(pos, val, node * 2, x, mid) + update1(pos, val, node * 2 + 1, mid + 1, y);
}
ll query(ll node, ll x, ll y,ll depth)
{
ll ch = seg[node];
ll mid = (x + y) / 2;
if (ch == 0 || ch == (y - x + 1)) {
return 0;
}
check[depth]++;
return query(node * 2, x, mid, depth + 1) + query(node * 2+1, mid+1, y, depth + 1)+2*(1<<(depth+1));
}
ll query1(ll node, ll x, ll y,ll depth)
{
ll ch = seg1[node];
ll mid = (x + y) / 2;
if (ch == 0 || ch == (y - x + 1)) {
return 0;
}
ll gap = 2 * (1 << (depth + 1));
return query1(node * 2, x, mid, depth + 1) + query1(node * 2 + 1, mid + 1, y, depth + 1) + gap-(gap/(1<<depth)*check[depth]);
}
int main()
{
scanf("%lld %lld", &n, &m);
for (ll i = 1; i <= m; i++)
{
memset(check, 0, sizeof(check));
ll q, w;
scanf("%lld %lld", &q, &w);
if (q == 0) {
cc[w] ^= 1;
update(w, cc[w], 1, 1, (1 << n));
}
else
{
cc1[w] ^= 1;
update1(w, cc1[w], 1, 1, (1 << n));
}
ll dap = query(1, 1, 1 << n, 0);
dap += query1(1, 1, (1 << n), 0);
printf("%lld\n", dap+1);
}
}