Submission #361133

#	Time	Username	Problem	Language	Result	Execution time	Memory
361133		NachoLibre	Horses (IOI15_horses)	C++17	100 / 100	620 ms	64876 KiB

horses

#include <bits/stdc++.h>
using namespace std;
#ifndef wambule
#include "horses.h"
#else
#endif

const int mod = 1e9 + 7;
const int MXY = 1e9;

int MG(int a, int b) {
	return 1ll * a * b % mod;
}

int G(int a, int b) {
	if(a == -1 || b == -1) return -1;
	if(1ll * a * b > MXY) return -1;
	return a * b;
}

struct ovo {
	ovo *l, *r;
	int a, x, y, xm, ym;
	ovo() {
		l = r = NULL;
		a = x = y = xm = ym = 1;
	}

	int AP() {
		return MG(a, xm);
	}

	void P() {
		if(l == NULL) l = new ovo();
		if(r == NULL) r = new ovo();
		int p = G(l->y, G(r->x, r->a));
		if(p == -1 || p > l->a) {
			a = r->a;
			x = G(l->x, G(l->y, r->x));
			y = r->y;
			xm = MG(l->xm, MG(l->ym, r->xm));
			ym = r->ym;
		} else {
			a = l->a;
			x = l->x;
			y = G(l->y, G(r->x, r->y));
			xm = l->xm;
			ym = MG(l->ym, MG(r->xm, r->ym));
		}
	}

	void C(int vl, int rm) {
		if(rm) a = vl;
		else x = xm = vl, y = ym = 1;
	}
} *rt;

int globn;
void gng(int si, int vl, int rm, int l = 0, int r = globn - 1, ovo *&t = rt) {
	if(t == NULL) t = new ovo();
	int m = (l + r) / 2;
	if(l == r) return t->C(vl, rm);
	else if(m >= si) gng(si, vl, rm, l, m, t->l);
	else gng(si, vl, rm, m + 1, r, t->r);
	return t->P();
}

int updateX(int i, int x) {
	gng(i, x, 0);
	return rt->AP();
}

int updateY(int i, int y) {
	gng(i, y, 1);
	return rt->AP();
}

int init(int n, int x[], int y[]) {
	rt = NULL, globn = n;
	for(int i = 0; i < n; ++i) {
		updateX(i, x[i]);
		updateY(i, y[i]);
	}
	return rt->AP();
}

#ifdef wambule
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	return 0;
}
#endif

Compilation message (stderr)

horses.cpp: In function 'int MG(int, int)':
horses.cpp:12:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   12 |  return 1ll * a * b % mod;
      |         ~~~~~~~~~~~~^~~~~

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