제출 #817353

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
817353		Boomyday	디지털 회로 (IOI22_circuit)	C++17	100 / 100	1008 ms	41824 KiB

circuit

//
// Created by adavy on 8/8/2023.
//
#include <vector>





//
// Created by adavy on 2/11/2023.
//
#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

using ll = long long;
using ld = long double;
using db = double;
using str = string; // yay python!

using ii = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;

using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vii = vector<ii>;
using vpl = vector<pl>;
using vpd = vector<pd>;

#define tcT template<class T
#define tcTU tcT, class U


// pairs
#define mp make_pair
#define f first
#define s second

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define len(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pb push_back
#define eb emplace_back
#define pf push_front

const int MOD = 1e9+2022; // 998244353;
const int MX = 2e5+5;
const ll INF = 1e18; // not too close to LLONG_MAX
const ld PI = acos((ld)-1);
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; // for every grid problem!!


struct Modular {
    int value;
    static const int MOD_value = MOD;

    Modular(long long v = 0) { value = v % MOD; if (value < 0) value += MOD;}

    Modular& operator+=(Modular const& b) {value += b.value; if (value >= MOD) value -= MOD; return *this;}
    Modular& operator-=(Modular const& b) {value -= b.value; if (value < 0) value += MOD;return *this;}
    Modular& operator*=(Modular const& b) {value = (long long)value * b.value % MOD;return *this;}


    friend Modular operator+(Modular a, Modular const b) { return a += b; }
    friend Modular operator-(Modular a, Modular const b) { return a -= b; }
    friend Modular operator-(Modular const a) { return 0 - a; }
    friend Modular operator*(Modular a, Modular const b) { return a *= b; }
    friend std::ostream& operator<<(std::ostream& os, Modular const& a) {return os << a.value;}
    friend bool operator==(Modular const& a, Modular const& b) {return a.value == b.value;}
    friend bool operator!=(Modular const& a, Modular const& b) {return a.value != b.value;}
};
#include "circuit.h"

vector<vi> cd;
int n, m;

vector<Modular> V,W; //values, weights


void dfs1(int nd){
    // calculate node weights
    if (nd >= n){
        W[nd] = 1;
        return;
    }
    W[nd]=1;
    trav(nei, cd[nd]){
        dfs1(nei);
        W[nd]*=W[nei];
    }
    W[nd]*=cd[nd].size();
}

void dfs2(int nd, Modular mpl){
    if (nd>=n){
        V[nd] = mpl; return;
    }
    vector<Modular> weights;
    trav(nei, cd[nd]) weights.pb(W[nei]);
    vector<Modular> left = {1}, right = {1};
    F0R(i, weights.size()) left.pb(left.back()*weights[i]);
    R0F(i, weights.size()) right.pb(right.back()*weights[i]);
    F0R(i, cd[nd].size())
        dfs2(cd[nd][i], mpl*left[i]*right[(cd[nd].size()-1)-i]);



}

vector<Modular> prefs = {0};
int ssz = 131072;
vector<Modular> seg(2*ssz,0); vi lz(2*ssz,0);



void pushdown(int rt, int tl, int tr){
    if (lz[rt]){
        seg[rt] = (prefs[tr+1]-prefs[tl])-seg[rt];
        lz[rt] = 0;
        if (tl!=tr){
            lz[2*rt]^=1;
            lz[2*rt+1]^=1;
        }
    }
}


void flip(int l, int r, int rt, int tl, int tr){
    pushdown(rt, tl, tr);
    if (r<tl || l > tr ) return;
    if (l<=tl && tr<=r) {
        lz[rt]^=1;
        pushdown(rt, tl, tr);
        return;
    }

    int tm = (tl+tr)>>1;
    flip(l, r, rt<<1, tl, tm);
    flip(l, r, (rt<<1)+1,tm+1,tr);
    seg[rt] = seg[rt<<1]+seg[(rt<<1)+1];
}

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
    cd.rsz(N);
    V.rsz(N + M);
    W.rsz(N + M);
    n = N;
    m = M;


    F0R(i, n + m) {
        if (i != 0) cd[P[i]].pb(i);
    }

    // calculate node values, node weights

    dfs1(0);
    dfs2(0, 1);

    FOR(i, n, n + m) {
        prefs.pb(prefs.back() + V[i]);
    }
    while(prefs.size()<=ssz){
        prefs.pb(prefs.back());
    }

    //trav(i, prefs) cout << i << " "; cout << endl;



    F0R(i, A.size()){
        if (A[i]) flip(i, i, 1, 0, ssz-1);
    }
   // cout << seg[1].value << endl;



}



int count_ways(int L, int R) {
    L-=n; R-=n;
    flip(L,R,1,0,ssz-1);
    return seg[1].value;

}


/*
#include <cassert>
#include <cstdio>

#include <vector>

int main() {
    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;
}

*/

컴파일 시 표준 에러 (stderr) 메시지

circuit.cpp: In function 'void dfs2(int, Modular)':
circuit.cpp:50:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Modular>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 | #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
      |                                        ^
circuit.cpp:51:18: note: in expansion of macro 'FOR'
   51 | #define F0R(i,a) FOR(i,0,a)
      |                  ^~~
circuit.cpp:124:5: note: in expansion of macro 'F0R'
  124 |     F0R(i, weights.size()) left.pb(left.back()*weights[i]);
      |     ^~~
circuit.cpp:50:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 | #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
      |                                        ^
circuit.cpp:51:18: note: in expansion of macro 'FOR'
   51 | #define F0R(i,a) FOR(i,0,a)
      |                  ^~~
circuit.cpp:126:5: note: in expansion of macro 'F0R'
  126 |     F0R(i, cd[nd].size())
      |     ^~~
circuit.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>)':
circuit.cpp:186:23: warning: comparison of integer expressions of different signedness: 'std::vector<Modular>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  186 |     while(prefs.size()<=ssz){
      |           ~~~~~~~~~~~~^~~~~
circuit.cpp:50:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 | #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
      |                                        ^
circuit.cpp:51:18: note: in expansion of macro 'FOR'
   51 | #define F0R(i,a) FOR(i,0,a)
      |                  ^~~
circuit.cpp:194:5: note: in expansion of macro 'F0R'
  194 |     F0R(i, A.size()){
      |     ^~~

• Subtask 1: 2 / 2
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 4 / 4
• Subtask 5: 12 / 12
• Subtask 6: 27 / 27
• Subtask 7: 28 / 28
• Subtask 8: 11 / 11