Submission #631988

#	Time	Username	Problem	Language	Result	Execution time	Memory
631988		minhcool	즐거운 사진 수집 (JOI13_collecting)	C++17	100 / 100	3828 ms	69104 KiB

collecting

#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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70