oj.uz

Submission #631988

# Submission time Handle Problem Language Result Execution time Memory
631988 2022-08-19T09:27:25 Z minhcool 즐거운 사진 수집 (JOI13_collecting) C++17
100 / 100
 3828 ms 69104 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";
            total *= 4;
            answer += (1LL << (n - i)) * (1LL << (n - i)) - (tol1[i + 1] * tol2[i + 1] * 4);
            //cout << answer << "\n";
            total += (tol1[i] * tol2[i] - total);
        }
        cout << answer << "\n";
    }
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	int t = 1;
	//cin >> t;
	while(t--) process();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 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 340 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 3 ms 340 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 4 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 5 ms 404 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 3828 ms 68756 KB Output is correct
2 Correct 3579 ms 68980 KB Output is correct
3 Correct 3268 ms 46248 KB Output is correct
4 Correct 3478 ms 69104 KB Output is correct
5 Correct 3529 ms 68544 KB Output is correct
6 Correct 3455 ms 67356 KB Output is correct
7 Correct 3468 ms 68904 KB Output is correct
8 Correct 3458 ms 68764 KB Output is correct
9 Correct 3201 ms 45360 KB Output is correct
10 Correct 3501 ms 46904 KB Output is correct
11 Correct 3502 ms 67980 KB Output is correct
12 Correct 3433 ms 67440 KB Output is correct
13 Correct 3311 ms 46872 KB Output is correct