Submission #1191901

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191901		DippleThree	Horses (IOI15_horses)	C++20	100 / 100	232 ms	45692 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
// typedef __int128 lll;

int pow2ceil(int n){
	n--;
	n |= n >> 1;
	n |= n >> 2;
	n |= n >> 4;
	n |= n >> 8;
	n |= n >> 16;
	return n + 1;
}

set<int> highx;
vector<ll> segy;
vector<ll> segx;
int n;
int N;
ll mod = 1e9 + 7;

ll solve(){
	ll sofar = 1;
	ll ans = 0;
	int ydemx = N + n-1;
	highx.insert(0);
	for (auto it = highx.rbegin(); it != highx.rend(); it++){
		int i = *it;
		ll x = segx[N + i];
		int l = N + i;
		int r = N + n - 1;
		ll y = segy[N + i];
		int ydex = N + i;
		while (l <= r){
			if (l % 2 == 1){
				if (y < segy[l]){
					y = segy[l];
					ydex = l;
				}
				l++;
			}
			if (r % 2 == 0){
				if (y < segy[r]){
					y = segy[r];
					ydex = r;
				}
				r--;
			}
			l /= 2;
			r /= 2;
		}
		if (y > ans){
			ans = y;
			ydemx = ydex;
		}
		ans *= x;
		sofar *= x;
		if (sofar >= mod) break;
	}
	while (ydemx < N){
		if (segy[ydemx] == segy[ydemx << 1]){
			ydemx = ydemx << 1;
		} else {
			ydemx = (ydemx << 1) | 1;
		}
	}
	ll toret = 1;
	int lto = N;
	int rto = ydemx;
	while (lto <= rto){
		if (lto % 2 == 1){
			toret = toret * segx[lto] % mod;
			lto++;
		}
		if (rto % 2 == 0){
			toret = toret * segx[rto] % mod;
			rto--;
		}
		lto /= 2;
		rto /= 2;
	}
	toret = toret * segy[ydemx] % mod;
	return toret;
}

int init(int np, int X[], int Y[]) {
	n = np;
	N = pow2ceil(n);
	segx.resize(2 * N);
	segy.resize(2 * N);
	for (int i = 0; i < n; i++) {
		segx[N + i] = X[i];
		segy[N + i] = Y[i];
	}
	for (int i = N - 1; i > 0; i--) {
		segx[i] = segx[i << 1] * segx[(i << 1) | 1] % mod;
		segy[i] = max(segy[i << 1], segy[(i << 1) | 1]);
	}
	for (int i = 0; i < n; i++) {
		if (X[i] > 1) {
			highx.insert(i);
		}
	}
	return solve();
}

int updateX(int pos, int val) {	
	if (highx.find(pos) != highx.end()){
		highx.erase(pos);
	}
	if (val > 1){
		highx.insert(pos);
	}
	segx[N + pos] = val;
	int i = N + pos;
	i /= 2;
	while (i > 0){
		segx[i] = segx[i << 1] * segx[(i << 1) | 1] % mod;
		i /= 2;
	}
	return solve();
}

int updateY(int pos, int val) {
	segy[N + pos] = val;
	int i = N + pos;
	i /= 2;
	while (i > 0){
		segy[i] = max(segy[i << 1], segy[(i << 1) | 1]);
		i /= 2;
	}
	return solve();
}

#ifdef LOCAL
static char _buffer[1024];
static int _currentChar = 0;
static int _charsNumber = 0;
static FILE *_inputFile, *_outputFile;

static inline int _read() {
    if (_charsNumber < 0) {
        exit(1);
    }
    if (!_charsNumber || _currentChar == _charsNumber) {
        _charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), _inputFile);
        _currentChar = 0;
    }
    if (_charsNumber <= 0) {
        return -1;
    }
    return _buffer[_currentChar++];
}

static inline int _readInt() {
    int c, x, s;
    c = _read();
    while (c <= 32) c = _read();
    x = 0;
    s = 1;
    if (c == '-') {
        s = -1;
        c = _read();
    }
    while (c > 32) {
        x *= 10;
        x += c - '0';
        c = _read();
    }
    if (s < 0) x = -x;
    return x;
}


int main() {
	_inputFile = fopen("horses.in", "rb");
	_outputFile = fopen("horses.out", "w");
	
	int N; N = _readInt();

	int *X = (int*)malloc(sizeof(int)*(unsigned int)N);
	int *Y = (int*)malloc(sizeof(int)*(unsigned int)N);

	for (int i = 0; i < N; i++) {
		X[i] = _readInt();
	}

	for (int i = 0; i < N; i++) {
		Y[i] = _readInt();
	}	

	fprintf(_outputFile,"%d\n",init(N,X,Y));

	int M; M = _readInt();

	for (int i = 0; i < M; i++) {
		int type; type = _readInt();
		int pos; pos = _readInt();
		int val; val = _readInt(); 

		if (type == 1) {
			fprintf(_outputFile,"%d\n",updateX(pos,val));
		} else if (type == 2) {
			fprintf(_outputFile,"%d\n",updateY(pos,val));
		}
	}

	return 0;
}
#endif

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 23 / 23
• Subtask 5: 23 / 23