oj.uz

답안 #628084

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
628084 2022-08-13T04:48:04 Z MarkBcc168 디지털 회로 (IOI22_circuit) C++17
6 / 100
 3000 ms 19732 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long

vector<ll> p_sum(100005,0), w(100005,0);

const ll mod = 1e9+2022;

struct Node{
    Node *l_child, *r_child;
    int l,r, sum; bool lazy;
    Node(){}
    Node(int _l, int _r){
        l = _l; r = _r; sum=0; lazy = false;
        int m = (l+r)/2;
        if(r-l > 1){
            l_child = new Node(l,m);
            r_child = new Node(m,r);
        }
        //cout << l << " " << r << "\n";
    }
    void push(){
        if(!lazy) return;
        if(r-l==1){
            lazy = false;
            sum = w[l] - sum;
        }
        else{
            lazy = false;
            if(l_child->lazy) l_child->push();
            if(r_child->lazy) r_child->push();
            l_child->lazy = true;
            r_child->lazy = true;
            sum = (p_sum[r] - p_sum[l] - sum + 2*mod);
            while(sum >= mod) sum -= mod;
        }
    }
    void flip(int L, int R){
        push();
        if(R <= l || L >= r) return; //not intersect
        else if(L <= l && r <= R) lazy = true;
        else if(r-l == 1){
            sum = w[l] - sum;
        }
        else{
            l_child->flip(L,R); r_child->flip(L,R);
            l_child->push(); r_child->push();
            sum = ((l_child->sum) + (r_child->sum));
            while(sum >= mod) sum -= mod;
        }
    }
    ll query(){
        push(); return sum;
    }
};

ll exp(ll a, ll n){
    if(n==0) return 1;
    if(n==1) return a%mod;
    ll x = exp(a, n/2);
    if(n%2==0) return (x*x)%mod;
    else return (((x*x)%mod)*a)%mod;
} 

const ll p = 2;
const ll q = 223;
const ll r = 2242157;
const ll phi = (p-1)*(q-1)*(r-1);

struct mint{
    int vp, vq; ll n;
    mint(ll _n){
        vp = 0; vq = 0;
        n = _n;
        while(n%p==0){vp++; n/=p;}
        while(n%q==0){vq++; n/=q;}
        n = n%mod;
    }
    mint(int _vp, int _vq, ll _n){
        vp = _vp; vq = _vq; n = _n%mod;
    }
    friend mint operator *(mint a, mint b){
        return mint(a.vp+b.vp, a.vq+b.vq, a.n*b.n);
    }
    mint inv(){
        return mint(-vp, -vq, exp(n,phi-1));
    }
    friend mint operator /(mint a, mint b){
        return a * b.inv();
    }
    ll to_int(){
        assert(vp >= 0 && vq >= 0);
        ll m=n;
        m = (m*exp(p,vp)) % mod;
        m = (m*exp(q,vq)) % mod;
        return m;
    }
};

int n,m;
Node tr(0,100005);

void init(int _n, int _m, std::vector<int> p, std::vector<int> a){
    n = _n; m = _m;
    //step 1: compute degree
    vector<int> adj[n];
    vector<int> d(n,0);
    vector<mint> d_mod(n,1);
    mint prod(1);
    for(int i=1; i<n+m; ++i){
        adj[p[i]].push_back(i);
        d[p[i]]++;
    }
    for(int i=0; i<n; ++i){
        d_mod[i] = mint(d[i]);
        prod = prod * d_mod[i];
    }
    //step 2: dfs to find weight of each leaf
    vector<mint> node_w(n+m, mint(1));
    node_w[0] = prod;

    vector<int> st(1,0);
    while(!st.empty()){
        int v = st[st.size()-1];
        st.pop_back();
        //cout << v << "\n";
        for(int u : adj[v]){
            node_w[u] = node_w[v] / d_mod[v];
            if(u < n) st.push_back(u);
        }
    }
    //step 3: build the tree
    p_sum[0] = 0;
    for(int i=0; i<m; ++i){
        w[i] = node_w[i+n].to_int();
        p_sum[i+1] = (p_sum[i] + w[i]) % mod;
    }
    for(int i=0; i<m; ++i){
        if(a[i] == 1) tr.flip(i,i+1);
    }
}
int count_ways(int l, int r){
    tr.flip(l-n,r-n+1);
    return tr.query();
}


/*int main(){
    for(int i=0; i<100; ++i){
        w[i] = i;
        p_sum[i+1] = p_sum[i] + w[i];
    }
    tr.flip(3,6);
    cout << tr.query() << "\n";
    tr.flip(5,10);
    cout << tr.query() << "\n";
}*/

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 11216 KB Output is correct
2 Correct 11 ms 11216 KB Output is correct
3 Correct 9 ms 11336 KB Output is correct
4 Correct 9 ms 11312 KB Output is correct
5 Correct 9 ms 11308 KB Output is correct
6 Correct 10 ms 11312 KB Output is correct
7 Correct 10 ms 11216 KB Output is correct
8 Correct 9 ms 11216 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 11216 KB Output is correct
2 Correct 11 ms 11216 KB Output is correct
3 Correct 9 ms 11336 KB Output is correct
4 Correct 9 ms 11312 KB Output is correct
5 Correct 9 ms 11308 KB Output is correct
6 Correct 10 ms 11312 KB Output is correct
7 Correct 10 ms 11216 KB Output is correct
8 Correct 9 ms 11216 KB Output is correct
9 Correct 9 ms 11216 KB Output is correct
10 Correct 9 ms 11268 KB Output is correct
11 Incorrect 9 ms 11340 KB 1st lines differ - on the 1st token, expected: '655368480', found: '360409272'
12 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 696 ms 15496 KB Output is correct
2 Correct 1000 ms 19732 KB Output is correct
3 Correct 1012 ms 19728 KB Output is correct
4 Correct 873 ms 19712 KB Output is correct

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 696 ms 15496 KB Output is correct
2 Correct 1000 ms 19732 KB Output is correct
3 Correct 1012 ms 19728 KB Output is correct
4 Correct 873 ms 19712 KB Output is correct
5 Execution timed out 3030 ms 15392 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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

Subtask #7
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 11216 KB Output is correct
2 Correct 11 ms 11216 KB Output is correct
3 Correct 9 ms 11336 KB Output is correct
4 Correct 9 ms 11312 KB Output is correct
5 Correct 9 ms 11308 KB Output is correct
6 Correct 10 ms 11312 KB Output is correct
7 Correct 10 ms 11216 KB Output is correct
8 Correct 9 ms 11216 KB Output is correct
9 Correct 9 ms 11216 KB Output is correct
10 Correct 9 ms 11268 KB Output is correct
11 Incorrect 9 ms 11340 KB 1st lines differ - on the 1st token, expected: '655368480', found: '360409272'
12 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 11216 KB Output is correct
2 Correct 11 ms 11216 KB Output is correct
3 Correct 9 ms 11336 KB Output is correct
4 Correct 9 ms 11312 KB Output is correct
5 Correct 9 ms 11308 KB Output is correct
6 Correct 10 ms 11312 KB Output is correct
7 Correct 10 ms 11216 KB Output is correct
8 Correct 9 ms 11216 KB Output is correct
9 Correct 9 ms 11216 KB Output is correct
10 Correct 9 ms 11268 KB Output is correct
11 Incorrect 9 ms 11340 KB 1st lines differ - on the 1st token, expected: '655368480', found: '360409272'
12 Halted 0 ms 0 KB -