#include<iostream>
#include<vector>
#include<array>
#include<algorithm>
int const MOD=10007;
struct Node{ // node({set of customers}).d[i] = number of ways for the set of
// customers to buy exactly i colored paintings
std::array<int,20> d;
int total;
Node(){}
Node(int a /* number of ways to buy colored painting*/,int b):d{{}},
total((a+b)%MOD){
d[0]=b%MOD;
d[1]=a%MOD;
}
Node(Node a,Node b):d{{}},total(a.total*b.total%MOD){
for(int i=0;i<a.d.size();++i)
for(int j=0;j+i<d.size();++j)
d[i+j]=(d[i+j]+a.d[i]*b.d[j])%MOD;
}
};
struct Tree{
std::vector<Node> nodes;
int index(int i)const{
/*
i+=1<<(31^__builtin_clz(nodes.size()));
if(i>=nodes.size())i-=nodes.size()/2;
*/
i+=nodes.size()/2;
return i;
}
Tree(std::vector<int> a,std::vector<int> b):nodes(2*a.size()){
for(int i=0;i<a.size();++i)
nodes[index(i)]=Node(a[i],b[i]);
for(int i=a.size();i-->1;)
nodes[i]=Node(nodes[i<<1],nodes[i<<1|1]);
}
void set(int i,int a,int b){
i=index(i);
nodes[i]=Node(a,b);
for(i>>=1;i!=0;i>>=1)
nodes[i]=Node(nodes[i<<1],nodes[i<<1|1]);
}
Node const& root()const{
return nodes[1];
}
};
int main(){
std::ios::sync_with_stdio(0);std::cin.tie(0);
int n,c;std::cin>>n>>c;
std::vector<int> a(n),b(n);
for(int i=0;i<n;++i){
std::cin>>a[i]>>b[i];
}
Tree tree(a,b);
int nquery;std::cin>>nquery;
while(nquery-->0){
int p,a,b;std::cin>>p>>a>>b;--p;
tree.set(p,a,b);
Node const& r=tree.root();
int total=r.total;
for(int i=0;i<c;++i){
total-=r.d[i];
}
total%=MOD;if(total<0)total+=MOD;
std::cout<<total<<'\n';
}
}
Compilation message
relativnost.cpp: In constructor 'Node::Node(Node, Node)':
relativnost.cpp:19:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<a.d.size();++i)
~^~~~~~~~~~~
relativnost.cpp:20:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j+i<d.size();++j)
~~~^~~~~~~~~
relativnost.cpp: In constructor 'Tree::Tree(std::vector<int>, std::vector<int>)':
relativnost.cpp:37:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<a.size();++i)
~^~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
9 ms |
512 KB |
Output isn't correct |
2 |
Incorrect |
16 ms |
512 KB |
Output isn't correct |
3 |
Incorrect |
9 ms |
484 KB |
Output isn't correct |
4 |
Incorrect |
703 ms |
9848 KB |
Output isn't correct |
5 |
Incorrect |
886 ms |
15864 KB |
Output isn't correct |
6 |
Incorrect |
723 ms |
16888 KB |
Output isn't correct |
7 |
Incorrect |
715 ms |
11768 KB |
Output isn't correct |
8 |
Incorrect |
797 ms |
16636 KB |
Output isn't correct |
9 |
Incorrect |
950 ms |
13688 KB |
Output isn't correct |
10 |
Incorrect |
997 ms |
13048 KB |
Output isn't correct |