oj.uz

Submission #631997

# Submission time Handle Problem Language Result Execution time Memory
631997 2022-08-19T09:35:14 Z minhcool 즐거운 사진 수집 (JOI13_collecting) C++17
100 / 100
 1205 ms 69004 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);
	cin.tie(0), cout.tie(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 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 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 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 2 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1079 ms 68788 KB Output is correct
2 Correct 1089 ms 68756 KB Output is correct
3 Correct 989 ms 46288 KB Output is correct
4 Correct 1171 ms 69004 KB Output is correct
5 Correct 1093 ms 68436 KB Output is correct
6 Correct 1164 ms 67404 KB Output is correct
7 Correct 1176 ms 68664 KB Output is correct
8 Correct 1109 ms 68808 KB Output is correct
9 Correct 964 ms 45392 KB Output is correct
10 Correct 966 ms 46928 KB Output is correct
11 Correct 1057 ms 67772 KB Output is correct
12 Correct 1128 ms 67400 KB Output is correct
13 Correct 1205 ms 46908 KB Output is correct