Submission #65747

#	Time	Username	Problem	Language	Result	Execution time	Memory
65747		Hoget157	Horses (IOI15_horses)	C++14	Compilation error	0 ms	0 KiB

horses

#include <bits/stdc++.h>
#define int long long
#define MOD 1000000007
using namespace std;

int n;

class RMQ{
	int seg,ini;
	vector<int> dat;
	function<int(int,int)> f;
	public:
	RMQ() : seg(1){}
	void init(int def,function<int(int,int)> F){
		ini = def;
		f = F;
		while(seg < n) seg *= 2;
		dat.resize(seg * 2 - 1);
		for(int i = 0;i < seg * 2 - 1;i++) dat[i] = ini;
	}
	void update(int i,int x){
		i += seg - 1;
		dat[i] = x;
		while(i){
			i = (i - 1) / 2;
			dat[i] = f(dat[i * 2 + 1],dat[i * 2 + 2]);
		}
	}
	int get(int a,int b,int k = 0,int l = 0,int r = -1){
		if(r == -1) r = seg;
		if(b <= l || r <= a) return ini;
		if(a <= l && r <= b) return dat[k];
		return f(get(a,b,k * 2 + 1,l,(l + r) / 2),get(a,b,k * 2 + 2,(l + r) / 2,r));
	}
	int find(int a,int b,bool isl,int k = 0,int l = 0,int r = -1){
		if(b == -1) b = seg;
		if(r == -1) r = seg;
		if(dat[k] == 1 || b <= l || r <= a) return -1;
		if(r - l == 1) return l;
		int lans = find(a,b,isl,k * 2 + 1,l,(l + r) / 2),rans = find(a,b,isl,k * 2 + 2,(l + r) / 2,r);
		if(isl){
			if(lans != -1) return lans;
			return rans;
		}else{
			if(rans != -1) return rans;
			return lans;
		}
	}
};

RMQ rmq1,rmq2,seki;

int calc(){
	int pos = n - 1,tmp = 1,ma = 0,ans;
	while(pos > 0){
		pos = rmq1.find(0,pos,false);
		if(tmp * rmq1.get(pos,pos + 1) > 1000000000) break;
	}
	ans = seki.get(0,pos + 1);
	tmp = 1;
	while(pos < n - 1){
		int nxt = rmq1.find(pos + 1,-1,true);
		ma = max(ma,tmp * rmq2.get(pos,nxt));
		tmp *= rmq1.get(nxt,nxt + 1);
		pos = nxt;
	}
	return ma * ans % MOD;
}

int init(int N,int x[],int y[]){
	n = N + 2;
	rmq1.init(0,[](int a,int b){ return max(a,b); });
	rmq2.init(0,[](int a,int b){ return max(a,b); });
	seki.init(1,[](int a,int b){ return a * b % MOD; });
	rmq1.update(0,MOD);
	rmq1.update(n - 1,MOD);
	for(int i = 0;i < n - 2;i++){
		rmq1.update(i + 1,x[i]);
		rmq2.update(i + 1,y[i]);
		seki.update(i + 1,x[i]);
	}
	return calc();
}

int updateX(int pos,int val){
	rmq1.update(pos + 1,val);
	seki.update(pos + 1,val);
	return calc();
}

int updateY(int pos,int val){
	rmq2.update(pos + 1,val);
	return calc();
}

signed main(){
	int N,m,x[500010],y[500010];
	cin >> N;
	for(int i = 0;i < N;i++) cin >> x[i];
	for(int i = 0;i < N;i++) cin >> y[i];
	cin >> m;
	cout << init(N,x,y) << endl;
	for(int i = 0;i < m;i++){
		int a,b,c;
		cin >> a >> b >> c;
		if(a == 1) cout << updateX(b,c) << endl;
		else cout << updateY(b,c) << endl;
	}
	return 0;
}

Compilation message (stderr)

/tmp/cciFEYKf.o: In function `main':
grader.c:(.text.startup+0x0): multiple definition of `main'
/tmp/cc9fWzGE.o:horses.cpp:(.text.startup+0x0): first defined here
/tmp/cciFEYKf.o: In function `main':
grader.c:(.text.startup+0x2db): undefined reference to `init(int, int*, int*)'
grader.c:(.text.startup+0x71a): undefined reference to `updateX(int, int)'
grader.c:(.text.startup+0x8a6): undefined reference to `updateY(int, int)'
collect2: error: ld returned 1 exit status