Submission #419126

#	Time	Username	Problem	Language	Result	Execution time	Memory
419126		AugustinasJucas	Towns (IOI15_towns)	C++14	Compilation error	0 ms	0 KiB

towns

#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
const long long mod = 1e9 + 7;
struct medis{
	struct node{
		int l, r;
		long long sand = 1;
		int vntCnt = 0;
		long long maxY = 0;
	};
	int n;
	int dbInd = 0;
	vector<node> tree;
	void build(int v){
		if(v >= n){
			tree[v].l = tree[v].r = dbInd++;
		}else{
			build(v*2); build(v*2+1);
			tree[v].l = tree[v*2].l;
			tree[v].r = tree[v*2+1].r;
		}
	}
	medis(int dd){
		n = dd;
		tree.resize(2*n+1);
		build(1);
	}
	void changeX(int v, int l, int r, int x){
		if(l <= tree[v].l && tree[v].r <= r){
			tree[v].sand = x;
			tree[v].vntCnt = (x == 1);
		}else if(r < tree[v].l || tree[v].r < l){
			return;
		}else{
			changeX(v*2, l, r, x);
			changeX(v*2+1, l, r, x);
			tree[v].sand = tree[v*2].sand * tree[v*2+1].sand % mod;
			tree[v].vntCnt = tree[v*2].vntCnt + tree[v*2+1].vntCnt;
		}
	}
	void changeY(int v, int l, int r, int x){
		if(l <= tree[v].l && tree[v].r <= r){
			tree[v].maxY = x;
		}else if(r < tree[v].l || tree[v].r < l){
			return;
		}else{
			changeY(v*2, l, r, x);
			changeY(v*2+1, l, r, x);
			tree[v].maxY = max(tree[v*2].maxY, tree[v*2+1].maxY);
		}
	}
	long long getSand(int v, int l, int r){
		if(l <= tree[v].l && tree[v].r <= r){
			return tree[v].sand;
		}else if(r < tree[v].l || tree[v].r < l){
			return 1;
		}else{
			return getSand(v*2, l, r) * getSand(v*2+1, l, r) % mod;
		}
	}
	long long getMax(int v, int l, int r){
		if(l <= tree[v].l && tree[v].r <= r){
			return tree[v].maxY;
		}else if(r < tree[v].l || tree[v].r < l){
			return 1;
		}else{
			return max(getMax(v*2, l, r), getMax(v*2+1, l, r));
		}
	}
	int get1(int v, int l, int r){
		if(l <= tree[v].l && tree[v].r <= r){
			return tree[v].vntCnt;
		}else if(r < tree[v].l || tree[v].r < l){
			return 0;
		}else{
			return get1(v*2, l, r) + get1(v*2+1, l, r);
		}
	}
};
const int dydis = 5e5 + 10;
medis tree(dydis);
int n;
pair<int, vector<pair<long long, long long> > > last30(int n){
	int lastNotIn = n-1;
	vector<pair<long long, long long> > ret;
	int r = 0;
	int l = 0;
	int mid = 0;
	int kk = 0;
	for(int i = 0; i < 62; i++){
		if(lastNotIn == -1) break;
		if(tree.getSand(1, lastNotIn, lastNotIn) == 1){
			int rt = lastNotIn;
			l = 0; r = lastNotIn;
		//	cout << "l = " << l << ", r = " << r << endl;
			while(l <= r){
				mid = (l + r) / 2;
				if(tree.get1(1, mid, lastNotIn) == lastNotIn-mid+1){
					rt = min(rt, mid);
		//			cout << mid  << " tinka " << endl;
					r = mid-1;
				}else{
					l = mid+1;
				}
			}
			ret.push_back({1, tree.getMax(1, rt, lastNotIn)});
			lastNotIn = rt-1;
		}else{
			ret.push_back({tree.getSand(1, lastNotIn, lastNotIn), tree.getMax(1, lastNotIn, lastNotIn)});
			lastNotIn--;
			kk++;
		}
		if(kk > 31) break;
	}
	reverse(ret.begin(), ret.end());
	long long bv = 1;
	if(lastNotIn != -1) bv = tree.getSand(1, lastNotIn, lastNotIn);
	return {bv, ret};
}


long long get(){
	auto rk = last30(n);
	long long h = rk.first;
	auto mas = rk.second;
//	cout << "h = " << h << ", poros: "; for(auto x : mas) cout << "{" << x.first << ", " << x.second << "},  ";
//	cout <<endl << endl;
	int curMax = 0;
	for(int i = 0; i < (int)mas.size(); i++){
		long long B = 1;
		//cout << "i = " << i << endl;
		bool did = 0;
		for(int j = i+1; j < (int) mas.size(); j++){
			B *= mas[j].first;
			if(mas[j].second >= mas[i].second){
			//	cout << "STAS!" << endl;
				curMax = j;
				did = 1;
				i = j-1; break;
			}
			long long turiButi = mas[i].second / mas[j].second + 1;
		//	cout << "turi buti bent " << turiButi << ", o B = " << B << endl;
			if(B >= turiButi){
			//	cout << "tai, daray suita!" << endl;
				i = j-1;
				did = 1;
				curMax = j;
				break;
			}
		}
		if(!did) break;

	}
	long long ret = h;
	for(int i = 0; i <= curMax; i++){
		ret = ret * mas[i].first % mod;
	}
	ret = ret * mas[curMax].second % mod;
	return ret;
}


int init(int N, int X[], int Y[]) {
	n = N;
	for(int i = 0; i < n; i++){
		tree.changeX(1, i, i, X[i]);
		tree.changeY(1, i, i, Y[i]);
	}
	
	return get();
}

int updateX(int pos, int val) {	
	tree.changeX(1, pos, pos, val);
	return get();
}

int updateY(int pos, int val) {
	tree.changeY(1, pos, pos, val);
	return get();
}
/*
3
2 1 3
3 2 1
*/

Compilation message (stderr)

towns.cpp:2:10: fatal error: horses.h: No such file or directory
    2 | #include "horses.h"
      |          ^~~~~~~~~~
compilation terminated.