oj.uz

Submission #16828

# Submission time Handle Problem Language Result Execution time Memory
16828 2015-10-02T11:58:22 Z gs14004 즐거운 사진 수집 (JOI13_collecting) C++14
100 / 100
 1349 ms 18104 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;

int n, q;

struct seg{
    int tree[1<<21];
    int cnts[20];
    void init(){
        for(int i=0; i<n; i++){
            cnts[i] = (1<<i);
        }
    }
    void flip(int x){
        x |= (1<<n);
        tree[x] ^= 1;
        for(int dep = n-1; dep >= 0; dep--){
            x >>= 1;
            if(tree[x] == (1 << (n - dep)) || tree[x] == 0){
                cnts[dep]--; // 
            }
            tree[x] = tree[2*x] + tree[2*x+1];
            if(tree[x] == (1 << (n - dep)) || tree[x] == 0){
                cnts[dep]++;
            }
        }
    }
}px, py;

int main(){
    scanf("%d %d",&n,&q);
    px.init();
    py.init();
    for(int i=0; i<q; i++){
        int t, p;
        scanf("%d %d",&t, &p);
        p--;
        if(t) px.flip(p);
        else py.flip(p);
        lint ret = 0;
        for(int i=0; i<n; i++){
            int rcnt = (1 << (n - i - 1));
            ret += 1ll * rcnt * rcnt - 1ll * px.cnts[n-1-i] * py.cnts[n-1-i];
        }
        printf("%lld\n",ret * 4 + 1);
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1263 ms 18104 KB Output is correct
2 Correct 1252 ms 18104 KB Output is correct
3 Correct 1121 ms 18104 KB Output is correct
4 Correct 1288 ms 18104 KB Output is correct
5 Correct 1349 ms 18104 KB Output is correct
6 Correct 1247 ms 18104 KB Output is correct
7 Correct 1276 ms 18104 KB Output is correct
8 Correct 1251 ms 18104 KB Output is correct
9 Correct 1149 ms 18104 KB Output is correct
10 Correct 1176 ms 18104 KB Output is correct
11 Correct 1232 ms 18104 KB Output is correct
12 Correct 1235 ms 18104 KB Output is correct
13 Correct 1186 ms 18104 KB Output is correct