Submission #98693

#	Time	Username	Problem	Language	Result	Execution time	Memory
98693		user202729	Relativnost (COCI15_relativnost)	C++17	0 / 140	997 ms	16888 KiB

relativnost

#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 (stderr)

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)
               ~^~~~~~~~~

• Subtask 1: 0 / 140