제출 #379347

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
379347		pavement	말 (IOI15_horses)	C++17	100 / 100	1140 ms	162796 KiB

horses

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

typedef long double ld;
typedef long long ll;
const int MOD = 1e9 + 7;

int N, X[500005], Y[500005];

struct node {
	node *left, *right;
	int S, E;
	ld pv;
	pair<ld, int> val;
	node(int _s, int _e) : S(_s), E(_e), pv(0) {
		if (S == E) {
			val = make_pair(0., S);
			return;
		}
		int M = (S + E) >> 1;
		left = new node(S, M);
		right = new node(M + 1, E);
		val = max(left->val, right->val);
	}
	void prop() {
		if (S == E || pv == 0.) return;
		left->pv += pv;
		left->val.first += pv;
		right->pv += pv;
		right->val.first += pv;
		pv = 0.;
	}
	void upd(int l, int r, ld v) {
		if (l > E || r < S) return;
		if (l <= S && E <= r) {
			val.first += v;
			pv += v;
			return;
		}
		prop();
		left->upd(l, r, v);
		right->upd(l, r, v);
		val = max(left->val, right->val);
	}
} *root;

struct node2 {
	node2 *left, *right;
	int S, E, val, pv;
	node2(int _s, int _e) : S(_s), E(_e), val(1), pv(1) {
		if (S == E) return;
		int M = (S + E) >> 1;
		left = new node2(S, M);
		right = new node2(M + 1, E);
	}
	void prop() {
		if (S == E || pv == 1) return;
		left->pv = ((ll)left->pv * (ll)pv) % MOD;
		left->val = ((ll)left->val * (ll)pv) % MOD;
		right->pv = ((ll)right->pv * (ll)pv) % MOD;
		right->val = ((ll)right->val * (ll)pv) % MOD;
		pv = 1;
	}
	void upd(int l, int r, int v) {
		if (l > E || r < S) return;
		if (l <= S && E <= r) {
			val = ((ll)val * (ll)v) % MOD;
			pv = ((ll)pv * (ll)v) % MOD;
			return;
		}
		prop();
		left->upd(l, r, v);
		right->upd(l, r, v);
	}
	int qry(int p) {
		if (S == E) return val;
		prop();
		int M = (S + E) >> 1;
		if (p <= M) return left->qry(p);
		else return right->qry(p);
	}
} *root2;

ld f(int n) {
	return log(n) / 9.;
}

int init(int _N, int _X[], int _Y[]) {
	N = _N;
	for (int i = 1; i <= N; i++) X[i] = _X[i - 1];
	for (int i = 1; i <= N; i++) Y[i] = _Y[i - 1];
	root = new node(1, N);
	for (int i = 1; i <= N; i++)
		root->upd(i, N, f(X[i])), root->upd(i, i, f(Y[i]));
	root2 = new node2(1, N);
	for (int i = 1; i <= N; i++)
		root2->upd(i, N, X[i]), root2->upd(i, i, Y[i]);
	return root2->qry(root->val.second);
}

ll exp_mod(ll a, ll b) {
	a %= MOD;
	b %= (MOD - 1);
	ll r = 1ll;
	while (b) {
		if (b & 1) r = r * a % MOD;
		a = a * a % MOD;
		b >>= 1ll;
	}
	assert(r <= INT_MAX);
	return r;
}

int updateX(int pos, int val) {
	pos++;
	root->upd(pos, N, -f(X[pos]));
	root2->upd(pos, N, exp_mod(X[pos], MOD - 2));
	X[pos] = val;
	root->upd(pos, N, f(X[pos]));
	root2->upd(pos, N, X[pos]);
	return root2->qry(root->val.second);
}

int updateY(int pos, int val) {
	pos++;
	root->upd(pos, pos, -f(Y[pos]));
	root2->upd(pos, pos, exp_mod(Y[pos], MOD - 2));
	Y[pos] = val;
	root->upd(pos, pos, f(Y[pos]));
	root2->upd(pos, pos, Y[pos]);
	return root2->qry(root->val.second);
}

컴파일 시 표준 에러 (stderr) 메시지

horses.cpp: In member function 'void node2::prop()':
horses.cpp:59:38: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   59 |   left->pv = ((ll)left->pv * (ll)pv) % MOD;
      |              ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:60:40: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   60 |   left->val = ((ll)left->val * (ll)pv) % MOD;
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:61:40: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   61 |   right->pv = ((ll)right->pv * (ll)pv) % MOD;
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:62:42: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   62 |   right->val = ((ll)right->val * (ll)pv) % MOD;
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In member function 'void node2::upd(int, int, int)':
horses.cpp:68:28: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   68 |    val = ((ll)val * (ll)v) % MOD;
      |          ~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:69:26: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   69 |    pv = ((ll)pv * (ll)v) % MOD;
      |         ~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:118:28: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  118 |  root2->upd(pos, N, exp_mod(X[pos], MOD - 2));
      |                     ~~~~~~~^~~~~~~~~~~~~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:128:30: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  128 |  root2->upd(pos, pos, exp_mod(Y[pos], MOD - 2));
      |                       ~~~~~~~^~~~~~~~~~~~~~~~~

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