Submission #869916

#	Time	Username	Problem	Language	Result	Execution time	Memory
869916		qin	Horses (IOI15_horses)	C++17	100 / 100	142 ms	71944 KiB

horses

#ifdef LOCAL
#else
#include "horses.h"
#endif
#include <bits/stdc++.h>
#define fi first
#define se second
#define ssize(x) int(x.size())
#define pn printf("\n")
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef double db;
int inf = 2e09; ll infll = 2e18; ll mod = 1e09+7;
vector<ll> X, Y; // UWAGA - GLOBALNIE ZADEKLAROWANE
int base = 1;
struct seg{
		struct Node{
				int opt; ll mul, mulp, muls; bool o, op, os;
				Node() : opt(0), mul(1), mulp(1), muls(1), o(0), op(0), os(0) {}
		};
		vector<Node> t;
		ll mulTmp; bool ovTmp; db proportionTmp;
		void merge(int i){
				t[i].mul = t[i<<1].mul*t[i<<1|1].mul; t[i].o = t[i].mul >= mod ? 1 : (t[i<<1].o|t[i<<1|1].o), t[i].mul %= mod;
				mulTmp = t[i<<1].muls*t[i<<1|1].mulp; ovTmp = mulTmp >= mod ? 1 : (t[i<<1].os|t[i<<1|1].op), mulTmp %= mod;
				if(!Y[t[i<<1|1].opt]) proportionTmp = -1;
				else proportionTmp = db(Y[t[i<<1].opt])/db(Y[t[i<<1|1].opt]);
				if((db(mulTmp) >= proportionTmp || ovTmp) && proportionTmp > 0){ //zwycieża późniejszy
						t[i].opt = t[i<<1|1].opt; 
						t[i].mulp = t[i<<1].mul*t[i<<1|1].mulp, t[i].op = t[i].mulp >= mod ? 1 : (t[i<<1].o|t[i<<1|1].op), t[i].mulp %= mod;
						t[i].muls = t[i<<1|1].muls, t[i].os = t[i<<1|1].os;
				}
				else{ // zwycięża wcześniejszy
						t[i].opt = t[i<<1].opt; 
						t[i].muls = t[i<<1].muls*t[i<<1|1].mul, t[i].os = t[i].muls >= mod ? 1 : (t[i<<1].os|t[i<<1|1].o), t[i].muls %= mod;
						t[i].mulp = t[i<<1].mulp, t[i].op = t[i<<1].op;
				}
		}
		void init(int n){
				while(base < n) base <<= 1;
				t.resize(base<<1);
				X.resize(base+1); Y.resize(base+1);
				//printf("%d\n", base);
				for(int i = 1; i <= n; ++i) t[i+base-1].opt = i, t[i+base-1].mul = X[i], t[i+base-1].mulp = X[i], t[i+base-1].muls = 1; //muls daje na 1, bo miedzy elementami obchodzi mnie tylko przedzial pomiedzy nimi
				for(int i = n+1; i <= base; ++i) X[i] = 1, Y[i] = 0, t[i+base-1].opt = i, t[i+base-1].mul = X[i], t[i+base-1].mulp = X[i], t[i+base-1].muls = 1;
				//exit(0);
				for(int i = base-1; i; --i) merge(i);
				
		}
		void update(int i){
				t[i+base-1].mul = X[i], t[i+base-1].mulp = X[i], t[i+base-1].muls = 1;
				for(i += base-1, i >>= 1; i; i >>= 1) merge(i);
		}
		int query(){ return int(Y[t[1].opt]*t[1].mulp % mod); }
		void print(){
				for(int i = 1; i < base<<1; ++i) printf("%d: %d, %lld %lld %lld\n", i, t[i].opt, t[i].mul, t[i].mulp, t[i].muls);
		}
} seg;
int updateX(int i, int val){ X[i+1] = val; seg.update(i+1); return seg.query(); }
int updateY(int i, int val){ Y[i+1] = val; seg.update(i+1); return seg.query(); }
int init(int n, int x[], int y[]){
		X.resize(n+1), Y.resize(n+1);
		for(int i = 1; i <= n; ++i) X[i] = x[i-1], Y[i] = y[i-1];
		seg.init(n);
		//seg.print();
		return seg.query();
}
#ifdef LOCAL
int main(){
		int T = 1;
		for(++T; --T; ){
				int n = 3, x[3] = {2, 1, 3}, y[3] = {3, 2, 1};
				printf("%d\n", init(n, x, y));
		}
		return 0;
}
#endif

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