제출 #310169

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
310169		tengiz05	말 (IOI15_horses)	C++17	17 / 100	85 ms	80504 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
typedef long double ld;
typedef long long ll;
using namespace std;
int n;
const int NN = 5e5+5;
const ll mod = 1e9+7;
ll a[NN];
ll b[NN];
//=============================================
ll binpow(ll p, ll q){
	if(q == 0)return 1ll;
	ll temp = binpow(p, q/2);
	temp *= temp;
	temp %= mod;
	if(q%2==1)temp *= p;
	return temp%mod;
}ll inver(ll p){
	return binpow(p, mod-2);
}//===============================================

struct Node {
	ld sum;
	ll mul;
};
Node neutral = {0, 1ll};
int sz;
vector<Node> t;
vector<Node> ans;
void build(){
	sz=1;
	while(sz<n)sz<<=1;
	t.assign(sz*2, neutral);
	ans.assign(sz*2, neutral);
	
	for(int i=0;i<n;i++){
		t[i+sz].sum = log2(a[i]);
		t[i+sz].mul = a[i];
	}for(int i=1;i<sz;i++){
		t[i+sz].sum += t[i+sz-1].sum;
		t[i+sz].mul *= t[i+sz-1].mul;t[i+sz].mul%=mod;
	}for(int i=0;i<sz;i++){
		ans[i+sz].sum = t[i+sz].sum+log2(b[i]);
		ans[i+sz].mul =(t[i+sz].mul*b[i])%mod;
	}for(int i=sz-1;i>0;i--){
		if(ans[i*2].sum > ans[i*2+1].sum){
			ans[i] = ans[i*2];
		}else {
			ans[i] = ans[i*2+1];
		}
	}
}
Node getpref(int i){
	ld ans = 0.;
	ll ansl = 1;
	for(i+=sz; i>0; i>>=1){
		ans += t[i].sum;
		ansl *= t[i].mul;ansl%=mod;
	}
	return {ans, ansl};
}
Node combine(Node f, Node s){
	return {f.sum+s.sum, (f.mul*s.mul)%mod};
}
void push(int L, int R, int node){
	if(R-L == 1)return;
	t[node*2] = combine(t[node], t[node*2]);
	t[node*2+1]=combine(t[node], t[node*2+1]);
	t[node] = neutral;
}
void modifyX(int l, int r, int L, int R, int val, int node){
	
}
void modifyY(int pos, int val){
	
}//===============================================


int init(int N, int X[], int Y[]) {
	n = N;
	for(int i=0;i<n;i++)a[i] = X[i];
	for(int i=0;i<n;i++)b[i] = Y[i];
	build();
	return ans[1].mul;
}

int updateX(int pos, int val) {	
	modifyX(pos, sz, 0, sz, val, 1);
	return ans[1].mul;
}

int updateY(int pos, int val) {
	modifyY(pos, val);
	return ans[1].mul;
}

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

horses.cpp: In function 'Node getpref(int)':
horses.cpp:55:5: warning: declaration of 'ans' shadows a global declaration [-Wshadow]
   55 |  ld ans = 0.;
      |     ^~~
horses.cpp:30:14: note: shadowed declaration is here
   30 | vector<Node> ans;
      |              ^~~
horses.cpp: In function 'void modifyX(int, int, int, int, int, int)':
horses.cpp:72:18: warning: unused parameter 'l' [-Wunused-parameter]
   72 | void modifyX(int l, int r, int L, int R, int val, int node){
      |              ~~~~^
horses.cpp:72:25: warning: unused parameter 'r' [-Wunused-parameter]
   72 | void modifyX(int l, int r, int L, int R, int val, int node){
      |                     ~~~~^
horses.cpp:72:32: warning: unused parameter 'L' [-Wunused-parameter]
   72 | void modifyX(int l, int r, int L, int R, int val, int node){
      |                            ~~~~^
horses.cpp:72:39: warning: unused parameter 'R' [-Wunused-parameter]
   72 | void modifyX(int l, int r, int L, int R, int val, int node){
      |                                   ~~~~^
horses.cpp:72:46: warning: unused parameter 'val' [-Wunused-parameter]
   72 | void modifyX(int l, int r, int L, int R, int val, int node){
      |                                          ~~~~^~~
horses.cpp:72:55: warning: unused parameter 'node' [-Wunused-parameter]
   72 | void modifyX(int l, int r, int L, int R, int val, int node){
      |                                                   ~~~~^~~~
horses.cpp: In function 'void modifyY(int, int)':
horses.cpp:75:18: warning: unused parameter 'pos' [-Wunused-parameter]
   75 | void modifyY(int pos, int val){
      |              ~~~~^~~
horses.cpp:75:27: warning: unused parameter 'val' [-Wunused-parameter]
   75 | void modifyY(int pos, int val){
      |                       ~~~~^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:85:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   85 |  return ans[1].mul;
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:90:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   90 |  return ans[1].mul;
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:95:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   95 |  return ans[1].mul;

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