oj.uz

Submission #43195

# Submission time Handle Problem Language Result Execution time Memory
43195 2018-03-10T14:20:17 Z smu201111192 즐거운 사진 수집 (JOI13_collecting) C++14
100 / 100
 2262 ms 60660 KB 
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = (1<<21);
const int dep = 22;
int n,q;
long long rtree[MAXN],ctree[MAXN];
long long rsum[MAXN],csum[MAXN];
void update(int node,int st,int ed,int pos,long long *tree,long long *sum,int dep){
    if(pos > ed || pos < st)return;
    if(st == ed){
        tree[node] ^= 1;
        return;
    }
    if(tree[node] == 0 || tree[node] == (1LL <<(n-dep))) sum[dep]--;
    update(node*2,st,(st+ed)/2,pos,tree,sum,dep+1);
    update(node*2+1,(st+ed)/2+1,ed,pos,tree,sum,dep+1);
    tree[node] = tree[node * 2] + tree[node * 2 +1];
    if(tree[node] == 0 || tree[node] == (1LL <<(n-dep))) sum[dep]++;
    return;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> q;
    for(int i = 0; i <= n; i++){
        rsum[i] = csum[i] = (1LL << i);
    }
    for(int i = 1; i <= q; i++){
        int type; int line;
        cin >> type >> line;
        if(type == 0) update(1,1,(1<<n),line,rtree,rsum,0);
        else update(1,1,(1<<n),line,ctree,csum,0);
        long long ret = 0;
        long long last = 0;
        for(int j = 0; j <= n; j++){
            long long a = 1<<j;
            long long b = 1<<j;
            ret += a * b;
            ret -= 4 * last;
            last = rsum[j] * csum[j];
        }
        cout<<ret<<"\n";
    }
    
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 1 ms 552 KB Output is correct
4 Correct 1 ms 552 KB Output is correct
5 Correct 2 ms 552 KB Output is correct
6 Correct 1 ms 552 KB Output is correct
7 Correct 1 ms 552 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 552 KB Output is correct
2 Correct 2 ms 552 KB Output is correct
3 Correct 4 ms 564 KB Output is correct
4 Correct 3 ms 712 KB Output is correct
5 Correct 4 ms 748 KB Output is correct
6 Correct 3 ms 748 KB Output is correct
7 Correct 2 ms 748 KB Output is correct
8 Correct 3 ms 748 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2262 ms 60204 KB Output is correct
2 Correct 2204 ms 60340 KB Output is correct
3 Correct 1948 ms 60340 KB Output is correct
4 Correct 2189 ms 60660 KB Output is correct
5 Correct 2191 ms 60660 KB Output is correct
6 Correct 2172 ms 60660 KB Output is correct
7 Correct 2224 ms 60660 KB Output is correct
8 Correct 2153 ms 60660 KB Output is correct
9 Correct 1906 ms 60660 KB Output is correct
10 Correct 1926 ms 60660 KB Output is correct
11 Correct 2167 ms 60660 KB Output is correct
12 Correct 2107 ms 60660 KB Output is correct
13 Correct 1882 ms 60660 KB Output is correct