oj.uz

Submission #711341

# Submission time Handle Problem Language Result Execution time Memory
711341 2023-03-16T16:16:50 Z Jarif_Rahman Digital Circuit (IOI22_circuit) C++17
16 / 100
 1027 ms 3500 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{
        int sum = 0, sz = 1;
        bool rev = 0;
        node(){
        }
        node operator+(node X){
            node rt;
            rt.sz = sz+X.sz;
            rt.sum = sum+X.sum;
            return rt;
        }
        void pushdown(node &X){
            if(!rev) return;
            X.rev^=rev;
            X.sum = X.sz-X.sum;
        }
    };
    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;
            v[nd].sum = v[nd].sz-v[nd].sum;
            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);
    }
    int get(){
        return v[1].sum;
    }
};

int n, m;
vector<int> P, A;
segtree s(0);
ll pw = 1;

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);
    for(int i = 0; i < n-__builtin_ctz(m); i++) pw*=2, pw%=md;
}

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

Subtask #1
0 / 2.0

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

Subtask #2
0 / 7.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 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '706880838', found: '106285552'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

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

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 680 ms 1852 KB Output is correct
2 Correct 733 ms 3384 KB Output is correct
3 Correct 748 ms 3388 KB Output is correct
4 Correct 741 ms 3392 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 680 ms 1852 KB Output is correct
2 Correct 733 ms 3384 KB Output is correct
3 Correct 748 ms 3388 KB Output is correct
4 Correct 741 ms 3392 KB Output is correct
5 Correct 516 ms 1852 KB Output is correct
6 Correct 1027 ms 3392 KB Output is correct
7 Correct 918 ms 3500 KB Output is correct
8 Correct 948 ms 3388 KB Output is correct
9 Correct 343 ms 336 KB Output is correct
10 Correct 921 ms 464 KB Output is correct
11 Correct 966 ms 464 KB Output is correct
12 Correct 956 ms 464 KB Output is correct

Subtask #6
0 / 27.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 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '706880838', found: '106285552'
7 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

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

Subtask #8
0 / 11.0

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