Submission #102789

#TimeUsernameProblemLanguageResultExecution timeMemory
102789njchung99즐거운 사진 수집 (JOI13_collecting)C++14
30 / 100
5096 ms41580 KiB
#include<cstdio> #include<algorithm> #include<cstring> #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); } }

Compilation message (stderr)

collecting.cpp:8:15: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
 ll cc[1 << 20 + 1];
            ~~~^~~
collecting.cpp:9:16: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
 ll cc1[1 << 20 + 1];
             ~~~^~~
collecting.cpp: In function 'int main()':
collecting.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
collecting.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld", &q, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...