oj.uz

Submission #711330

# Submission time Handle Problem Language Result Execution time Memory
711330 2023-03-16T15:23:40 Z Jarif_Rahman Digital Circuit (IOI22_circuit) C++17
16 / 100
 1051 ms 7064 KB 
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

const ll md = 1000002022;

struct segtree{
    struct node{
        ll A, B, Ar, Br;
        bool rev = 0;
        node(){
            A = 0, B = 1, Ar = 1, Br = 0;
        }
        node operator+(node X){
            node rt;
            rt.A = (A*X.B)%md + (X.A*B)%md + (A*X.A*2LL)%md;
            rt.A%=md;
            rt.B = (A*X.B)%md + (X.A*B)%md + (B*X.B*2LL)%md;
            rt.B%=md;
            rt.Ar = (Ar*X.Br)%md + (X.Ar*Br)%md + (Ar*X.Ar*2LL)%md;
            rt.Ar%=md;
            rt.Br = (Ar*X.Br)%md + (X.Ar*Br)%md + (Br*X.Br*2LL)%md;
            rt.Br%=md;
            return rt;
        }
        void pushdown(node &X){
            if(!rev) return;
            X.rev^=rev;
            swap(X.A, X.Ar);
            swap(X.B, X.Br);
        }
    };
    int k;
    vector<node> v;
    segtree(int n){
        k = 1;
        while(k < n) k*=2;
        v.resize(2*k, node());
        for(int i = k-1; i > 0; i--) v[i] = v[2*i]+v[2*i+1];
    }
    void update(int l, int r, int nd, int a, int b){
        if(a > r || b < l) return;
        if(a >= l && b <= r){
            v[nd].rev^=1;
            swap(v[nd].A, v[nd].Ar);
            swap(v[nd].B, v[nd].Br);
            return;
        }
        int mid = (a+b)/2;
        v[nd].pushdown(v[2*nd]);
        v[nd].pushdown(v[2*nd+1]);
        v[nd].rev = 0;
        update(l, r, 2*nd, a, mid);
        update(l, r, 2*nd+1, mid+1, b);
        v[nd] = v[2*nd]+v[2*nd+1];
    }
    void update(int l, int r){
        update(l, r, 1, 0, k-1);
    }
    ll get(){
        return v[1].A;
    }
};

int n, m;
vector<int> P, A;
segtree s(0);

void init(int _n, int _m, vector<int> _P, vector<int> _A){
    swap(n, _n), swap(m, _m), swap(P, _P), swap(A, _A);
    s = segtree(m);
    for(int i = 0; i < m; i++) if(A[i]) s.update(i, i);
}

int count_ways(int L, int R){
    s.update(L-n, R-n);
    return s.get();
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '509', found: '896509654'
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 388 KB Output is correct
6 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '706880838', found: '475885760'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '509', found: '896509654'
4 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 726 ms 3664 KB Output is correct
2 Correct 711 ms 6980 KB Output is correct
3 Correct 1042 ms 6980 KB Output is correct
4 Correct 773 ms 7064 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 726 ms 3664 KB Output is correct
2 Correct 711 ms 6980 KB Output is correct
3 Correct 1042 ms 6980 KB Output is correct
4 Correct 773 ms 7064 KB Output is correct
5 Correct 820 ms 3644 KB Output is correct
6 Correct 923 ms 6984 KB Output is correct
7 Correct 1051 ms 6980 KB Output is correct
8 Correct 1031 ms 6980 KB Output is correct
9 Correct 445 ms 420 KB Output is correct
10 Correct 779 ms 720 KB Output is correct
11 Correct 964 ms 676 KB Output is correct
12 Correct 1008 ms 720 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 388 KB Output is correct
6 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '706880838', found: '475885760'
7 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '509', found: '896509654'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '509', found: '896509654'
4 Halted 0 ms 0 KB -