제출 #924837

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
924837		Macker	말 (IOI15_horses)	C++17	100 / 100	284 ms	91220 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
typedef long double ld;
#define fi first
#define se second

ll mod = 1e9 + 7;
vector<pair<ll, ld>> st;
vector<pair<ll, ld>> lz;
vector<ll> x;
vector<ll> y;
int n;
int len = 1;

ll pow(ll n, ll k){
	n %= mod;
	ll res = 1;
	while(k > 0){
		if(k % 2) res = res * n % mod;
		k /= 2;
		n = n * n % mod;
	}
	return res;
}

ll modInv(ll x){
	return pow(x, mod - 2);
}

void prop(int i){
	st[i * 2].fi = st[i * 2].fi * lz[i].fi % mod;
	st[i * 2].se += lz[i].se;
	lz[i * 2].fi = lz[i * 2].fi * lz[i].fi % mod;
	lz[i * 2].se += lz[i].se;
	st[i * 2 + 1].fi = st[i * 2 + 1].fi * lz[i].fi % mod;
	st[i * 2 + 1].se += lz[i].se;
	lz[i * 2 + 1].fi = lz[i * 2 + 1].fi * lz[i].fi % mod;
	lz[i * 2 + 1].se += lz[i].se;
	lz[i] = {1, 0};
}

void upd(int l, int r, ll mval, ld lval, int i = 1, int s = 0, int e = len){
	if(l >= e || s >= r) return;
	if(l <= s && e <= r){
		st[i].fi = st[i].fi * mval % mod;
		st[i].se += lval;
		lz[i].fi = lz[i].fi * mval % mod;
		lz[i].se += lval;
		return;
	}
	prop(i);
	upd(l, r, mval, lval, i * 2, s, (s + e) / 2);
	upd(l, r, mval, lval, i * 2 + 1, (s + e) / 2, e);
	if(st[i * 2].second > st[i * 2 + 1].second){
		st[i] = st[i * 2];
	}
	else st[i] = st[i * 2 + 1];
}

int init(int N, int X[], int Y[]) {
	x.assign(X, X + N);
	y.assign(Y, Y + N);
	n = N;

	while(len < N) len *= 2;
	st.resize(2 * len, {1, 0});
	lz.resize(2 * len, {1, 0});

	for (int i = 0; i < N; i++) {
		st[len + i].fi = st[len + i - 1].fi * x[i] % mod;
		st[len + i].second = st[len + i - 1].se + logl(x[i]);
	}
	for (int i = 0; i < N; i++) {
		st[len + i].fi = st[len + i].fi * y[i] % mod;
		st[len + i].se += logl(y[i]);
	}
	
	for (int i = len - 1; i > 0; i--) {
		if(st[i * 2].second > st[i * 2 + 1].second){
			st[i] = st[i * 2];
		}
		else st[i] = st[i * 2 + 1];
	}
	
	
	return st[1].first;
}

int updateX(int pos, int val) {
	upd(pos, len + 1, val * modInv(x[pos]) % mod, logl(val) - logl(x[pos]));
	x[pos] = val;

	return st[1].first;
}

int updateY(int pos, int val) {
	upd(pos, pos + 1, val * modInv(y[pos]) % mod, logl(val) - logl(y[pos]));
	y[pos] = val;

	return st[1].first;
}

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

horses.cpp: In function 'll pow(ll, ll)':
horses.cpp:19:11: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   19 | ll pow(ll n, ll k){
      |        ~~~^
horses.cpp:16:5: note: shadowed declaration is here
   16 | int n;
      |     ^
horses.cpp: In function 'll modInv(ll)':
horses.cpp:30:14: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   30 | ll modInv(ll x){
      |           ~~~^
horses.cpp:14:12: note: shadowed declaration is here
   14 | vector<ll> x;
      |            ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:90:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   90 |  return st[1].first;
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:97:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   97 |  return st[1].first;
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:104:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  104 |  return st[1].first;

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