제출 #1010679

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

circuit

#include<bits/stdc++.h>
#include<fstream>
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
const ld PI = 3.14159265359, prec = 1e-9;;
//using u128 = __uint128_t;
const int cox[4] = {1, 0, -1, 0};
const int coy[4] = {0, -1, 0, 1};
const ll mod =  1000002022, pr = 31;
const int mxn = 2e5 + 5, mxd = 250 * 250, sq = 500, mxv = 2e6 + 1;
const int max_iter = 8e4, global_iter = 15e5 + 5;
//const int base = (1 <<18);
const ll inf = 1e9 + 5, neg = -69420, inf2 = 1e14;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
// have fun!
//#include "circuit.h"

#include <vector>
int n, m;
vt<int>adj[mxn + 1];
ll sub[mxn + 1], val[mxn + 1], pref[mxn + 1], suf[mxn + 1], a[mxn + 1];
ll st[4 * mxn + 1], sm[4 * mxn + 1];
bool lz[4 * mxn + 1];
void dfs(int s){
    sub[s] = 1;
    for(auto i: adj[s]){
        dfs(i); sub[s] = (sub[s] * sub[i]) % mod;
    }
    if(sz(adj[s])){
        sub[s] = (sub[s] * sz(adj[s])) % mod;
    }
}
void dfs2(int s, ll mul){
    if(s >= n)val[s - n] = mul;
	vt<ll>pref(sz(adj[s]) + 1), suf(sz(adj[s]) + 1);
    pref[0] = 1;
    for(int i = 0; i < sz(adj[s]); i++){
        pref[i + 1] = (pref[i] * sub[adj[s][i]]) % mod;
    }
    suf[sz(adj[s])] = 1;
    for(int i = sz(adj[s]) - 1; i >= 0; i--){
        suf[i] = (suf[i + 1] * sub[adj[s][i]]) % mod;
    }
    for(int i = 0; i < sz(adj[s]); i++){
        ll cool = (pref[i] * suf[i + 1]) % mod;
        dfs2(adj[s][i], (mul * cool) % mod);
    }
}
void pull(int nd){
    st[nd] = (st[nd << 1] + st[nd << 1 | 1]) % mod;
    sm[nd] = (sm[nd << 1] + sm[nd << 1 | 1]) % mod;
}
void build(int nd, int l, int r){
    if(l == r){
        st[nd] = a[l] * val[l]; sm[nd] = val[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(nd << 1, l, mid); build(nd << 1 | 1, mid + 1, r);
    pull(nd);
}
void go(int nd){
    st[nd] = (sm[nd] - st[nd] + mod) % mod; lz[nd] ^= 1;
}
void push(int nd){
    if(!lz[nd])return;
    go(nd << 1); go(nd << 1 | 1);
	lz[nd] = 0;
}
void upd(int nd, int l, int r, int ql, int qr){
    if(ql > r || qr < l)return;
    if(ql <= l && qr >= r){
        go(nd); 
        return;
    }
    push(nd);
    int mid = (l + r) >> 1;
    upd(nd << 1, l, mid, ql, qr); upd(nd << 1 | 1, mid + 1, r, ql, qr);
    pull(nd);
    
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
    n = N; m = M;
    for(int i = 1; i < n + m; i++){
        adj[P[i]].pb(i);
    }
    for(int i = 0; i < m; i++){
        a[i] = A[i];
    }
    dfs(0); dfs2(0, 1);
    build(1, 0, m - 1);
}

int count_ways(int L, int R) {
    upd(1, 0, m - 1, L - n, R - n);
  return(st[1]);
}

 
 /*
//#include "circuit.h"

#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;
}
*/

• 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