제출 #1024572

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1024572		vjudge1	디지털 회로 (IOI22_circuit)	C++17	16 / 100	722 ms	10328 KiB

circuit

#include <bits/stdc++.h>
#define ent '\n'
#define f first
#define s second

using namespace std;
typedef long long ll;
const int maxn = 2e5 + 12;
const int mod = 1e9 + 2022;

pair<ll, ll> t[maxn*4];
vector<int> g[maxn];
int p[maxn];
int a[maxn];
int n, m;

pair<ll, ll> merge(pair<ll, ll> a, pair<ll, ll> b){
    pair<ll, ll> ans = {0, 0};
    ans.f += a.f * b.f * 2 + a.f * b.s + a.s * b.f;
    ans.s += a.s * b.s * 2 + a.f * b.s + a.s * b.f;
    ans.f %= mod, ans.s %= mod;
    return ans;
}

void build(int v, int tl, int tr){
    p[v] = 0;
    if(tl == tr){
        if(a[tl]) t[v] = {0, 1};
        else t[v] = {1, 0};
    }
    else{
        int mid = tl + tr >> 1;
        build(v*2, tl, mid);
        build(v*2+1, mid+1, tr);
        t[v] = merge(t[v*2], t[v*2+1]);
    }
}

void push(int v, int tl, int tr){
    if(tl == tr || !p[v]){
        return;
    }
    p[v*2] ^= 1;
    p[v*2+1] ^= 1;
    swap(t[v*2].f, t[v*2].s);
    swap(t[v*2+1].f, t[v*2+1].s);
    p[v] = 0;
}

void upd(int v, int tl, int tr, int l, int r){
    push(v, tl, tr);
    if(tl > r || l > tr){
        return;
    }
    if(tl >= l && tr <= r){
        swap(t[v].f, t[v].s);
        p[v] = 1;
        return;
    }
    int mid = tl + tr >> 1;
    upd(v*2, tl, mid, l, r);
    upd(v*2+1, mid+1, tr, l, r);
    t[v] = merge(t[v*2], t[v*2+1]);
}

void init(int N, int M, std::vector<int> P, std::vector<int> A){
    n = M, m = N;
    for(int i=1;i<=n;i++){
        a[i] = A[i-1];
    }
    build(1, 1, n);
}

int count_ways(int L, int R){
    L -= m - 1;
    R -= m - 1;
    upd(1, 1, n, L, R);
    return t[1].s;
}

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

circuit.cpp: In function 'void build(int, int, int)':
circuit.cpp:32:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |         int mid = tl + tr >> 1;
      |                   ~~~^~~~
circuit.cpp: In function 'void upd(int, int, int, int, int)':
circuit.cpp:60:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |     int mid = tl + tr >> 1;
      |               ~~~^~~~

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