Submission #631996

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

collecting

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
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){
    int temp = (!IT1[id] ? 1 : -1);
    IT1[id] ^= 1;
    int lay = 0;
    while(id){
        id >>= 1;
        if(!id) return;
        lay++;
        bool ck = !(IT1[id] & ((1LL << lay) - 1));
        tol1[lay] -= ck;
        //cout << ck << "\n";
        IT1[id] += temp;
        ck = !(IT1[id] & ((1LL << lay) - 1));
        //cout << ck << "\n";
        tol1[lay] += ck;
    }
}

void upd2(int id){
    int temp = (!IT2[id] ? 1 : -1);
    IT2[id] ^= 1;
    int lay = 0;
    while(id){
        id >>= 1;
        if(!id) return;
        lay++;
        bool ck = !(IT2[id] & ((1LL << lay) - 1));
        tol2[lay] -= ck;
        IT2[id] += temp;
        ck = !(IT2[id] & ((1LL << lay) - 1));
        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 (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70