Submission #153939

#TimeUsernameProblemLanguageResultExecution timeMemory
153939ivandasfsHorses (IOI15_horses)C++14
Compilation error
0 ms0 KiB
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

typedef long long ll;

ll init(int m, int *v, int *w);
ll updateX(int pos, int val);
ll updateY(int pos, int val);

const ll MOD = 1e9+7;

vector <ll> X;
vector <ll> Y;

set <pair<int, int> > jed;

ll umno[3000005];
ll maxi[3000005];

int n;
int off;


void umno_update(int node, ll val) {
	if (!node) return ;
	if (node >= off) {
		umno[node] = val;
	} else {
		umno[node] = (umno[node*2] * umno[node*2+1]) % MOD;
	}
	umno_update(node/2, val);
}

ll umno_query(int x, int y, int l, int r, int node) {
	if (l>y or r<x) return 1LL;
	if (l>=x and r<=y) return umno[node];
	return (umno_query(x, y, l, (l+r)/2, node*2) * umno_query(x, y, (l+r)/2+1, r, node*2+1)) % MOD;
}

void maxi_update(int node, ll val) {
	if (!node) return ;
	if (node >= off) {
		maxi[node] = val;
	} else {
		maxi[node] = max(maxi[node*2], maxi[node*2+1]);
	}
	maxi_update(node/2, val);
}

ll maxi_query(int x, int y, int l, int r, int node) {
	if (l>y or r<x) return 0LL;
	if (l>=x and r<=x) return maxi[node];
	return max(maxi_query(x, y, l, (l+r)/2, node*2), maxi_query(x, y, (l+r)/2+1, r, node*2+1));
}

ll init(int m, int *v, int *w) {
	n = m;
	off = 1;
	while (off<n) off*=2;
	for (int i=0 ; i<n ; i++) {
		X.push_back(v[i]);
		Y.push_back(w[i]);
		umno_update(i+off, X[i]);
		maxi_update(i+off, Y[i]);
	}
	X.push_back(-1);
	for (int i=0 ; i<n ; i++) {
		if (X[i]==1) {
			int st = i;
			while (X[i]==1) i++;
			jed.insert(make_pair(st, i-1));
		}
	}
	X.pop_back();
	ll suff = 1;
	bool over = false;
	for (int i=n-1 ; i>=0 ; i--) {
		if (over) {
			return (umno_query(0, i, 0, off-1, 1) * suff) % MOD;
		}
		suff = max(suff * X[i], Y[i] * X[i]);
		if (suff >= MOD) {
			over = true;
			suff %= MOD;
		}
	}
	return suff;
}

ll calculate() {
	ll suff = 1;
	bool over = false;
	for (int i=n-1 ; i>=0 ; i--) {
		if (over) {
			return (umno_query(0, i, 0, off-1, 1) * suff) % MOD;
		}
		if (X[i] == 1) {
			set <pair<int, int> > :: iterator it = jed.lower_bound(make_pair(i, i+1));
			it--;
	//		cout << it -> first << "     " << it -> second << endl;
			ll best = maxi_query(it -> first, it -> second, 0, off-1, 1);
			suff = max(suff, best);
			i = (it -> first);
		} else {
			suff = max(suff * X[i], Y[i] * X[i]);
			if (suff >= MOD) {
				over = true;
				suff %= MOD;
			}
		}
	//	cout <<"suff = "<<suff<<endl;
	}
	return suff;
}

ll updateX(int pos, ll val) {
	int bio = X[pos];
	X[pos] = val;
	umno_update(pos+off, val);
	if (bio == 1) {
		set <pair<int, int> > :: iterator it = jed.lower_bound(make_pair(pos, 10000000));
		it--;
		pair <int, int> p = *it;
		pair <int, int> l = make_pair(p.first, pos-1);
		pair <int, int> r = make_pair(pos+1, p.second);
		jed.erase(it);
		if (l.first <= l.second) jed.insert(l);
		if (r.first <= r.second) jed.insert(r);
	}
	if (val == 1) {
		jed.insert(make_pair(pos, pos));
		set <pair <int, int> > :: iterator l, r, it;
		it = jed.lower_bound(make_pair(pos, pos));
		r = it;
		l = it;
		if (l != jed.begin()) {
			l--;
			if (l -> second == pos - 1) {
				pair <int, int> newp = make_pair(l -> first, pos);
				jed.erase(l);
				jed.erase(it);
				jed.insert(newp);
				it = jed.find(newp);
			}
		}
		r++;
		if (r != jed.end()) {
			if (r -> first == pos+1) {
				pair <int, int> newp = make_pair(it -> first, r -> second);
				jed.erase(it);
				jed.erase(r);
				jed.insert(newp);
			}
		}
	}
	return calculate();
}

ll updateY(int pos, ll val) {
	Y[pos] = val;
	maxi_update(pos+off, val);
	return calculate();
}
/*
int main() {
	int m;
	cin >>m;
	vector <int> a;
	vector <int> b;
	for (int i=0 ; i<m ; i++) {
		int x;
		cin >>x;
		a.push_back(x);
	}
	for (int i=0 ; i<m ; i++) {
		int x;
		cin >>x;
		b.push_back(x);
	}
	cout <<init(m, a, b)<<endl;
	int q;
	cin >>q;
	for (int i=0 ; i<q ; i++) {
		char c;
		int pos, val;
		cin >>c>>pos>>val;
		if (c=='X') cout <<updateX(pos, val)<<endl;
		else cout <<updateY(pos, val)<<endl;
	}
	return 0;
}
*/

Compilation message (stderr)

horses.cpp: In function 'll updateX(int, ll)':
horses.cpp:121:17: warning: conversion to 'int' from '__gnu_cxx::__alloc_traits<std::allocator<long long int> >::value_type {aka long long int}' may alter its value [-Wconversion]
  int bio = X[pos];
                 ^
/tmp/ccgswZq3.o: In function `main':
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