oj.uz

답안 #1058029

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1058029 2024-08-14T08:02:48 Z dozer 디지털 회로 (IOI22_circuit) C++17
50 / 100
 653 ms 33612 KB 
#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define pii pair<int, int>
#define st first
#define nd second
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define LL node * 2
#define RR node * 2 + 1
#define ll long long
#define MAXN 500005

const int modulo = 1000002022;
const ll INF = 2e18 + 7;

int add(ll a, ll b){
    if (a + b < modulo) return a + b;
    return a + b - modulo;
}

int subs(ll a, ll b){
    if (a < b) return a - b + modulo;
    return a - b;
}

int mul(ll a, ll b){
    return (a * b) % modulo;
}

int fe(ll a, ll b){
    if (b == 0) return 1;
    if (b % 2) return mul(a, fe(a, b - 1));
    int tmp = fe(a, b / 2);
    return mul(tmp, tmp);
}


struct SegTree{
    vector<int> t, lazy, arr, sum;
    int n;

    void build(int node, int l, int r){
        if (l == r){
            sum[node] = arr[l];
            t[node] = 0;
            return;
        }
        int mid = (l + r) / 2;
        build(LL, l, mid);
        build(RR, mid + 1, r);
        sum[node] = add(sum[LL], sum[RR]);
        t[node] = 0;
    }

    void push(int node, int l, int r){
        if (lazy[node] == 0) return;
        t[node] = subs(sum[node], t[node]);
        lazy[node] = 0;
        if (l != r) lazy[LL] ^= 1, lazy[RR] ^= 1;
    }

    void update(int node, int l, int r, int sl, int sr){
        push(node, l, r);
        if (l > sr || r < sl) return;
        if (l >= sl && r <= sr){
            lazy[node] ^= 1;
            push(node, l, r);
            return;
        }

        int mid = (l + r) / 2;
        update(LL, l, mid, sl, sr);
        update(RR, mid + 1, r, sl, sr);
        t[node] = add(t[LL], t[RR]);
    }


    int query(int node, int l, int r, int sl, int sr){
        push(node, l, r);
        if (l > sr || r < sl) return 0;
        if (l >= sl && r <= sr) return t[node];
        int mid = (l + r) / 2;
        return add(query(LL, l, mid, sl, sr), query(RR, mid + 1, r, sl, sr));
    }


    SegTree(int N, vector<int> a){
        n = N;
        t.resize(4 * n + 5, 0), lazy.resize(4 * n + 5, 0), sum.resize(4 * n + 5, 0);
        arr = a;
        build(1, 0, n - 1);
    }
};

vector<int> adj[MAXN];
int val[MAXN], sz[MAXN], n, m;

void dfs(int node){
    sz[node] = 0;
    if (node < n) sz[node]++;
    for (auto i : adj[node]){
        dfs(i);
        sz[node] += sz[i];
    }
}


void dfs2(int node, int x){
    val[node] = x;
    if (adj[node].empty()) return;
    else if (adj[node].size() == 2){
        int l = adj[node][0], r = adj[node][1];
        dfs2(l, mul(x, fe(2, sz[r])));
        dfs2(r, mul(x, fe(2, sz[l])));
    }
}


SegTree *T;

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
    n = N, m = M;
    for (int i = 1; i < n + m; i++)
        adj[P[i]].pb(i);

    dfs(0);
    dfs2(0, 1);

    vector<int> arr(m);
    for (int i = 0; i < m; i++) arr[i] = val[i + n];
        
    T = new SegTree(m, arr);
    for (int i = 0; i < m; i++) 
        if (A[i]) T->update(1, 0, m - 1, i, i);
}

int count_ways(int L, int R) {
    T->update(1, 0, m - 1, L - n, R - n);
    return T->query(1, 0, m - 1, 0, m - 1);
}

/*
int main() {
    fileio();
    int N, M, Q;
    assert(3 == scanf("%d %d %d", &N, &M, &Q));
    std::vector<int> P(N + M), A(M);
    for (int i = 0; i < N + M; ++i) {
    assert(1 == scanf("%d", &P[i]));
    }
    for (int j = 0; j < M; ++j) {
    assert(1 == scanf("%d", &A[j]));
    }
    init(N, M, P, A);

    for (int i = 0; i < Q; ++i) {
    int L, R;
    assert(2 == scanf("%d %d", &L, &R));
    printf("%d\n", count_ways(L, R));
    }
    return 0;
}*/

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 15704 KB Output is correct
2 Incorrect 2 ms 15704 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 15704 KB Output is correct
2 Correct 2 ms 15704 KB Output is correct
3 Correct 3 ms 15960 KB Output is correct
4 Correct 2 ms 15960 KB Output is correct
5 Correct 3 ms 15960 KB Output is correct
6 Correct 2 ms 15960 KB Output is correct
7 Correct 2 ms 15960 KB Output is correct
8 Correct 2 ms 15960 KB Output is correct
9 Correct 3 ms 15960 KB Output is correct
10 Correct 3 ms 15956 KB Output is correct
11 Correct 2 ms 15956 KB Output is correct
12 Correct 2 ms 15960 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 15704 KB Output is correct
2 Incorrect 2 ms 15704 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 381 ms 19800 KB Output is correct
2 Correct 505 ms 23384 KB Output is correct
3 Correct 545 ms 23384 KB Output is correct
4 Correct 487 ms 23352 KB Output is correct

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 381 ms 19800 KB Output is correct
2 Correct 505 ms 23384 KB Output is correct
3 Correct 545 ms 23384 KB Output is correct
4 Correct 487 ms 23352 KB Output is correct
5 Correct 443 ms 19800 KB Output is correct
6 Correct 510 ms 23524 KB Output is correct
7 Correct 476 ms 23384 KB Output is correct
8 Correct 554 ms 23296 KB Output is correct
9 Correct 202 ms 15960 KB Output is correct
10 Correct 444 ms 16304 KB Output is correct
11 Correct 453 ms 16416 KB Output is correct
12 Correct 548 ms 16216 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 15704 KB Output is correct
2 Correct 2 ms 15704 KB Output is correct
3 Correct 3 ms 15960 KB Output is correct
4 Correct 2 ms 15960 KB Output is correct
5 Correct 3 ms 15960 KB Output is correct
6 Correct 2 ms 15960 KB Output is correct
7 Correct 2 ms 15960 KB Output is correct
8 Correct 2 ms 15960 KB Output is correct
9 Correct 3 ms 15960 KB Output is correct
10 Correct 3 ms 15956 KB Output is correct
11 Correct 2 ms 15956 KB Output is correct
12 Correct 2 ms 15960 KB Output is correct
13 Correct 381 ms 19800 KB Output is correct
14 Correct 505 ms 23384 KB Output is correct
15 Correct 545 ms 23384 KB Output is correct
16 Correct 487 ms 23352 KB Output is correct
17 Correct 443 ms 19800 KB Output is correct
18 Correct 510 ms 23524 KB Output is correct
19 Correct 476 ms 23384 KB Output is correct
20 Correct 554 ms 23296 KB Output is correct
21 Correct 202 ms 15960 KB Output is correct
22 Correct 444 ms 16304 KB Output is correct
23 Correct 453 ms 16416 KB Output is correct
24 Correct 548 ms 16216 KB Output is correct
25 Correct 614 ms 27052 KB Output is correct
26 Correct 614 ms 27396 KB Output is correct
27 Correct 653 ms 27416 KB Output is correct
28 Correct 463 ms 27224 KB Output is correct
29 Correct 598 ms 33480 KB Output is correct
30 Correct 616 ms 33612 KB Output is correct

Subtask #7
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 15704 KB Output is correct
2 Incorrect 2 ms 15704 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 15704 KB Output is correct
2 Incorrect 2 ms 15704 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -