oj.uz

Submission #631991

# Submission time Handle Problem Language Result Execution time Memory
631991 2022-08-19T09:28:34 Z minhcool 즐거운 사진 수집 (JOI13_collecting) C++17
100 / 100
 3700 ms 69156 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define y1 y11
#define int long long
#define fi first
#define se second
#define pb push_back
//#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = (1LL << 20);
 
const int oo = 1e18 + 7, mod = 1e9 + 7;

int n, q;

int IT1[N << 1], IT2[N << 1];
int tol1[N], tol2[N];

int pos[N << 1];

void trav(int id, int l, int r){
    if(l == r){
        pos[l] = id;
        return;
    }
    int mid = (l + r) >> 1;
    trav(id << 1, l, mid);
    trav(id << 1 | 1, mid + 1, r);
}

void upd1(int id){
    IT1[id] ^= 1;
    int lay = 0;
    while(id){
        id >>= 1;
        if(!id) return;
        lay++;
        bool ck = (IT1[id] == 0 || IT1[id] == (1LL << lay));
        tol1[lay] -= ck;
        IT1[id] = IT1[id << 1] + IT1[id << 1 | 1];
        ck = (IT1[id] == 0 || IT1[id] == (1LL << lay));
        tol1[lay] += ck;
    }
}

void upd2(int id){
    IT2[id] ^= 1;
    int lay = 0;
    while(id){
        id >>= 1;
        if(!id) return;
        lay++;
        bool ck = (IT2[id] == 0 || IT2[id] == (1LL << lay));
        tol2[lay] -= ck;
        IT2[id] = IT2[id << 1] + IT2[id << 1 | 1];
        ck = (IT2[id] == 0 || IT2[id] == (1LL << lay));
        tol2[lay] += ck;
    }
}

void process(){
    cin >> n >> q;
    trav(1, 1, (1LL << n));
    for(int i = 0; i <= n; i++){
        tol1[i] = tol2[i] = (1LL << (n - i));
    }
    while(q--){
        int type, x;
        cin >> type >> x;
        if(type == 0) upd1(pos[x]);
        else upd2(pos[x]);
        int total = 0, answer = 0;
        for(int i = n; i >= 0; i--){
            //cout << tol1[i] << " " << tol2[i] << "\n";
            answer += (1LL << (2 * (n - i)))  - (tol1[i + 1] * tol2[i + 1] * 4);
            //cout << answer << "\n";
        }
        cout << answer << "\n";
    }
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	int t = 1;
	//cin >> t;
	while(t--) process();
}

Compilation message

collecting.cpp: In function 'void process()':
collecting.cpp:79:13: warning: unused variable 'total' [-Wunused-variable]
   79 |         int total = 0, answer = 0;
      |             ^~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 3542 ms 68784 KB Output is correct
2 Correct 3627 ms 68660 KB Output is correct
3 Correct 3700 ms 46200 KB Output is correct
4 Correct 3536 ms 69156 KB Output is correct
5 Correct 3531 ms 68560 KB Output is correct
6 Correct 3418 ms 67564 KB Output is correct
7 Correct 3453 ms 68896 KB Output is correct
8 Correct 3469 ms 68760 KB Output is correct
9 Correct 3311 ms 45400 KB Output is correct
10 Correct 3281 ms 47148 KB Output is correct
11 Correct 3284 ms 67932 KB Output is correct
12 Correct 3329 ms 67644 KB Output is correct
13 Correct 3207 ms 46852 KB Output is correct