Submission #1255207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255207		ZeroCool	Horses (IOI15_horses)	C++20	100 / 100	125 ms	54188 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 5e5 + 20;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 1;

int A[N], B[N];

namespace seggy{

	struct Node{
		int prod, opt, suf, pref;
		
		Node(int i){
			prod = pref = A[i];
			suf = 1;
			opt = i;
		}
		Node(){
			
		}
	};
	
	Node operator+(Node a,Node b){
		Node res;
		int p = min(INF, a.suf * b.pref);
		p = min(INF, p * B[b.opt]);
		if(p > B[a.opt]){
			res = b;
			res.pref = min(INF, res.pref * a.prod);
		}else{
			res = a;
			res.suf = min(INF, res.suf * b.prod);
		}
		res.prod = min(INF, a.prod * b.prod);
		return res;
	}

	Node s[4 * N];
	int p[4 * N];

	void bld(int k,int tl,int tr){
		if(tl == tr){
			s[k] = Node(tl);
			p[k] = A[tl];
			return;
		}
		int tm = (tl +tr) / 2;
		bld(k * 2, tl, tm);
		bld(k * 2 + 1, tm + 1, tr);
		s[k] = s[k * 2] + s[k * 2 + 1];
		p[k] = (p[k * 2] * p[k * 2 + 1]) % MOD;
	}

	void upd(int k,int tl,int tr,int i){
		if(tl == tr){
			s[k] = Node(tl);
			p[k] = A[tl];
			return;
		}
		int tm = (tl + tr) / 2;
		if(i <= tm)upd(k * 2, tl, tm, i);
		else upd(k * 2 + 1, tm + 1, tr, i);
		s[k] = s[k * 2] + s[k * 2 + 1];
		p[k] = (p[k * 2] * p[k * 2 + 1]) % MOD;
	}
	int qry(int k,int tl,int tr,int l,int r){
		if(l > tr || tl > r)return 1;
		if(l <= tl && tr <= r)return p[k];
		int tm = (tl + tr) / 2;
		return (qry(k * 2, tl, tm, l, r) * qry(k * 2 + 1, tm + 1, tr, l, r)) % MOD;
	}


};

int n;

signed init(signed _n, signed X[], signed Y[]) {
	n = _n;
	for(int i = 0;i < n;i++)A[i] = X[i], B[i] = Y[i];
	seggy::bld(1, 0, n - 1);
	int i = seggy::s[1].opt;
	return (seggy::qry(1, 0, n - 1, 0, i) * B[i]) % MOD;
}

signed updateX(signed pos, signed val) {	
	A[pos] = val;
	seggy::upd(1, 0, n - 1, pos);
	int i = seggy::s[1].opt;
	return (seggy::qry(1, 0, n - 1, 0, i) * B[i]) % MOD;
}

signed updateY(signed pos, signed val) {
	B[pos] = val;
	seggy::upd(1, 0, n - 1, pos);
	int i = seggy::s[1].opt;
	return (seggy::qry(1, 0, n - 1, 0, i) * B[i]) % MOD;
}

#define int signed

Compilation message (stderr)

horses.cpp:104: warning: "int" redefined
  104 | #define int signed
      | 
horses.cpp:4: note: this is the location of the previous definition
    4 | #define int long long
      |

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