oj.uz

Submission #631975

# Submission time Handle Problem Language Result Execution time Memory
631975 2022-08-19T09:18:33 Z minhcool 즐거운 사진 수집 (JOI13_collecting) C++17
100 / 100
 3957 ms 78324 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];

void upd1(int id, int l, int r, int pos, int lay){
    if(l == r){
        IT1[id] ^= 1;
        return;
    }
    bool ck = (IT1[id] == 0 || IT1[id] == (1LL << lay));
    tol1[lay] -= ck;
    int mid = (l + r) >> 1;
    if(pos <= mid) upd1(id << 1, l, mid, pos, lay - 1);
    else upd1(id << 1 | 1, mid + 1, r, pos, lay - 1);
    IT1[id] = IT1[id << 1] + IT1[id << 1 | 1];
    ck = (IT1[id] == 0 || IT1[id] == (1LL << lay));
    tol1[lay] += ck;
}

void upd2(int id, int l, int r, int pos, int lay){
    if(l == r){
        IT2[id] ^= 1;
        return;
    }
    bool ck = (IT2[id] == 0 || IT2[id] == (1LL << lay));
    tol2[lay] -= ck;
    int mid = (l + r) >> 1;
    if(pos <= mid) upd2(id << 1, l, mid, pos, lay - 1);
    else upd2(id << 1 | 1, mid + 1, r, pos, lay - 1);
    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;
    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(1, 1, (1LL << n), x, n);
        else upd2(1, 1, (1LL << n), x, n);
        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 1 ms 332 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 328 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 4 ms 340 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 6 ms 412 KB Output is correct
5 Correct 5 ms 340 KB Output is correct
6 Correct 4 ms 408 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Correct 6 ms 340 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 3606 ms 78244 KB Output is correct
2 Correct 3628 ms 78096 KB Output is correct
3 Correct 3859 ms 58812 KB Output is correct
4 Correct 3764 ms 78324 KB Output is correct
5 Correct 3626 ms 77840 KB Output is correct
6 Correct 3781 ms 76668 KB Output is correct
7 Correct 3957 ms 77956 KB Output is correct
8 Correct 3708 ms 77948 KB Output is correct
9 Correct 3285 ms 57392 KB Output is correct
10 Correct 3527 ms 60020 KB Output is correct
11 Correct 3585 ms 76808 KB Output is correct
12 Correct 3681 ms 76796 KB Output is correct
13 Correct 3578 ms 60068 KB Output is correct