oj.uz

Submission #631996

# Submission time Handle Problem Language Result Execution time Memory
631996 2022-08-19T09:34:45 Z minhcool 즐거운 사진 수집 (JOI13_collecting) C++17
100 / 100
 3843 ms 69168 KB 
#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

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.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 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 3 ms 340 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Correct 3 ms 340 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 3576 ms 68816 KB Output is correct
2 Correct 3470 ms 68720 KB Output is correct
3 Correct 3253 ms 46228 KB Output is correct
4 Correct 3450 ms 69168 KB Output is correct
5 Correct 3565 ms 68460 KB Output is correct
6 Correct 3451 ms 67436 KB Output is correct
7 Correct 3843 ms 68664 KB Output is correct
8 Correct 3673 ms 68716 KB Output is correct
9 Correct 3409 ms 45272 KB Output is correct
10 Correct 3485 ms 46868 KB Output is correct
11 Correct 3522 ms 67860 KB Output is correct
12 Correct 3631 ms 67472 KB Output is correct
13 Correct 3514 ms 46820 KB Output is correct