Submission #1058089

#TimeUsernameProblemLanguageResultExecution timeMemory
1058089tolbiDigital Circuit (IOI22_circuit)C++17
0 / 100
317 ms2612 KiB
#include "circuit.h" #include <bits/stdc++.h> using namespace std; constexpr int MAXN = 100000; constexpr int MOD = 1e9+2022; void prep(array<int,2> &a, array<int,2> &b, array<int,2> &c){ int sif = (1ll*b[0]*c[0])%MOD; int bir = ((1ll*b[0]*c[1])%MOD)+((1ll*b[1]*c[0])%MOD); if (bir>=MOD) bir-=MOD; int iki = (1ll*b[1]*c[1])%MOD; a[0]=(2ll*sif+bir)%MOD; a[1]=(2ll*iki+bir)%MOD; } struct SegTree{ int tag[MAXN]; array<int,2> ans[MAXN], rev[MAXN]; int sz; void upd(int node){ prep(ans[node],ans[node*2+1],ans[node*2+2]); prep(rev[node],rev[node*2+1],rev[node*2+2]); } void dallan(int node){ if (tag[node]){ swap(ans[node],rev[node]); if (node*2+1<sz){ tag[node*2+1]^=1; tag[node*2+2]^=1; } tag[node]=0; } } SegTree(vector<int> arr):sz(arr.size()*2-1){ fill(tag,tag+sz,0); for (int i = 0; i < arr.size(); i++){ ans[i+sz/2][arr[i]]=1; ans[i+sz/2][arr[i]^1]=0; rev[i+sz/2]=ans[i+sz/2]; swap(rev[i+sz/2][0],rev[i+sz/2][1]); } for (int i = sz/2-1; i >= 0; i--){ upd(i); } } void update(int tl, int tr, int l = 0, int r = -1, int node = 0){ if (r==-1) r = sz/2; dallan(node); if (tl>=l && tr<=r){ return tag[node]=1,dallan(node); } if (l>tr || r<tl) return; int mid = l+(r-l)/2; if (tl<=mid) update(tl,tr,l,mid,node*2+1); else dallan(node*2+1); if (mid<tr) update(tl,tr,mid+1,r,node*2+2); else dallan(node*2+2); upd(node); } } *segtree=nullptr; int n; void init(int N, int M, std::vector<int> P, std::vector<int> A) { n=N; segtree=new SegTree(A); } int count_ways(int L, int R) { L-=n,R-=n; segtree->update(L,R); return (segtree->ans)[0][1]; }

Compilation message (stderr)

circuit.cpp: In constructor 'SegTree::SegTree(std::vector<int>)':
circuit.cpp:36:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   for (int i = 0; i < arr.size(); i++){
      |                   ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...