oj.uz

Submission #650799

# Submission time Handle Problem Language Result Execution time Memory
650799 2022-10-15T11:42:40 Z ShirleyM Digital Circuit (IOI22_circuit) C++17
16 / 100
 1010 ms 11856 KB 
#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<bool> vb;
typedef vector<vb> vvb;
#define x first
#define y second
#define pb push_back
#define loop(i,s,e) for(int i=s;i<e;i++)
#define loopr(i,s,e) for(int i=e-1;i>=s;i--)
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define all(a) a.begin(),a.end()

const int mod = 1000002022;
const int mx_m = 1e5;

int n,m;
vi a;

struct node{
    int cnt0=0, cnt1=0;
    bool flag=0;

    node(int cnt0=0, int cnt1=0):cnt0(cnt0), cnt1(cnt1){}
};

node seg[4*mx_m];

void set_(int ind){
    swap(seg[ind].cnt0, seg[ind].cnt1);
    seg[ind].flag = !seg[ind].flag;
}

void push(int ind){
    if(seg[ind].flag){
        set_(2*ind);
        set_(2*ind+1);
        seg[ind].flag=0;
    }
}

void pull(int ind){
    seg[ind].cnt1 = ((seg[2*ind].cnt0 * seg[2*ind+1].cnt1) + (seg[2*ind].cnt1 * seg[2*ind+1].cnt0) + (2*seg[2*ind].cnt1*seg[2*ind+1].cnt1))%mod;
    seg[ind].cnt0 = ((seg[2*ind].cnt0 * seg[2*ind+1].cnt1) + (seg[2*ind].cnt1 * seg[2*ind+1].cnt0) + (2*seg[2*ind].cnt0*seg[2*ind+1].cnt0))%mod;
}

void build(int ind, int l, int r){
    if(l+1==r){
        int cnt0 = 0, cnt1=1;
        if(!a[l]) swap(cnt0, cnt1);
        seg[ind] = node(cnt0, cnt1);
        return;
    }
    int mid = (l+r)/2;
    build(2*ind, l, mid);
    build(2*ind+1, mid, r);
    pull(ind);
}

 void update_swap(int ind, int l, int r, int a, int b){
        if(a<=l && r<=b){
            set_(ind);
            return;
        }
        if(l>=b || r<=a) return;
        int mid = (l+r)/2;
        push(ind);
        update_swap(2*ind, l, mid, a,b);
        update_swap(2*ind+1, mid, r, a,b);
        pull(ind);
 }

 int query(){
     return seg[1].cnt1;
 }


void init(int32_t N, int32_t M, std::vector<int32_t> P, std::vector<int32_t> A) {
    n=N;m=M;
    a.resize(m);
    loop(i,0,m){
        a[i] = A[i];
    }
    build(1,0,m);
}

int32_t count_ways(int32_t L, int32_t R) {
    int l=L, r=R;
    l-=n; r-=n;
    update_swap(1,0,m,l,r+1);
    return query();

}

Subtask #1
0 / 2.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 9.0

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

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 508 ms 10712 KB Output is correct
2 Correct 814 ms 11720 KB Output is correct
3 Correct 1010 ms 11720 KB Output is correct
4 Correct 772 ms 11712 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 508 ms 10712 KB Output is correct
2 Correct 814 ms 11720 KB Output is correct
3 Correct 1010 ms 11720 KB Output is correct
4 Correct 772 ms 11712 KB Output is correct
5 Correct 726 ms 10704 KB Output is correct
6 Correct 785 ms 11716 KB Output is correct
7 Correct 891 ms 11720 KB Output is correct
8 Correct 806 ms 11856 KB Output is correct
9 Correct 391 ms 9740 KB Output is correct
10 Correct 822 ms 9804 KB Output is correct
11 Correct 583 ms 9808 KB Output is correct
12 Correct 858 ms 9796 KB Output is correct

Subtask #6
0 / 27.0

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

Subtask #7
0 / 28.0

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

Subtask #8
0 / 11.0

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