제출 #1086978

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1086978		the_coding_pooh	Horses (IOI15_horses)	C++14	0 / 100	213 ms	41584 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define uwu return;

using namespace std;

const int SIZE = 5e5 + 5,  MOD = 1e9 + 7;

long long in_X[SIZE], in_Y[SIZE]; 

#define lc 2 * id
#define rc 2 * id + 1

struct ratio_query{
	long long rq_seg[4 * SIZE];
	
	void pull(int id){
		if(rq_seg[lc] == MOD || rq_seg[rc] == MOD) 
			rq_seg[id] = MOD;
		else{
			rq_seg[id] = rq_seg[lc] * rq_seg[rc];
			if(rq_seg[id] >= MOD) 
				rq_seg[id] = MOD;
		}
	}

	void build(int L, int R, int id){
		if(L == R){
			rq_seg[id] = in_X[L];
			return;
		}
		int M = (L + R) / 2;
		build(L, M, lc);
		build(M + 1, R, rc);
		pull(id);
		return;
	}

	void modify(int pos, int val, int L, int R, int id){
		if(L == R){
			in_X[pos] = val;
			rq_seg[id] = val;
			return;
		}

		int M = (L + R) / 2;
		if(pos <= M)
			modify(pos, val, L, M, lc);
		else
			modify(pos, val, M + 1, R, rc);
		pull(id);
		return;
	}

	long long query(int ql, int qr, int L, int R, int id){
		if(ql <= L && R <= qr){
			return rq_seg[id];
		}
		int M = (L + R) / 2;
		long long retl = 1, retr = 1;
		if(ql <= M) 
			retl = query(ql, min(M, qr), L, M, lc);
		if(qr > M)
			retr = query(max(ql, M + 1), qr, M + 1, R, rc);
		if(retl == MOD || retr == MOD) 
			return MOD;
		return (retl * retr >= MOD ? MOD : retl * retr);
	}
}rq;

struct node{
	long long pi_X, mx_tm, mx_pos;
}SEGTree[SIZE];

#define nd SEGTree[id]
#define ln SEGTree[lc]
#define rn SEGTree[rc]

void pull(int id){
	long long tms = rq.query(ln.mx_pos + 1, rn.mx_pos, 0, SIZE - 1, 1);
	if(tms == MOD || tms * in_Y[rn.mx_pos] >= in_Y[ln.mx_pos]){
		nd.mx_tm = (ln.pi_X * rn.mx_tm) % MOD;
		nd.mx_pos = rn.mx_pos;
	}
	else{
		nd.mx_tm = ln.mx_tm;
		nd.mx_pos = ln.mx_pos;
	}
	nd.pi_X = (ln.pi_X * rn.pi_X) % MOD;
	return;
}


void build(int L, int R, int id){
	if(L == R){
		SEGTree[id].pi_X = in_X[L];
		SEGTree[id].mx_tm = (in_X[L] * in_Y[L]) % MOD; 
		SEGTree[id].mx_pos = L;
		return;
	}
	int M = (L + R) / 2;
	build(L, M, lc);
	build(M + 1, R, rc);
	pull(id);
	return;
}

void modify(int pos, int val, bool is_X, int L, int R, int id){
	if(L == R){
		if(is_X){
			in_X[pos] = val;
			SEGTree[id].pi_X = in_X[L];
			SEGTree[id].mx_tm = (in_X[L] * in_Y[L]) % MOD; 
			rq.modify(pos, val, 0, SIZE - 1, 1);
		}
		else{
			in_Y[pos] = val;
			SEGTree[id].mx_tm = (in_X[L] * in_Y[L]) % MOD; 
		}
		return;
	}
	int M = (L + R) / 2;
	if(pos <= M)
		modify(pos, val, is_X, L, M, lc);
	else
		modify(pos, val, is_X, M + 1, R, rc);
	pull(id);
	return;
}

int init(int N, int X[], int Y[]) {
	for(int i = 0; i < N; i++){
		in_X[i] = X[i];
		in_Y[i] = Y[i];
	}
	rq.build(0, SIZE - 1, 1);
	build(0, SIZE - 1, 1);
	return SEGTree[1].mx_tm;
}

int updateX(int pos, int val) {	
	modify(pos, val, 1, 0, SIZE - 1, 1);
	return SEGTree[1].mx_tm;
}

int updateY(int pos, int val) {
	modify(pos, val, 0, 0, SIZE - 1, 1);
	return SEGTree[1].mx_tm;
}

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

horses.cpp: In function 'void pull(int)':
horses.cpp:80:37: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   80 |  long long tms = rq.query(ln.mx_pos + 1, rn.mx_pos, 0, SIZE - 1, 1);
      |                                     ^
horses.cpp:80:45: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   80 |  long long tms = rq.query(ln.mx_pos + 1, rn.mx_pos, 0, SIZE - 1, 1);
      |                                             ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:138:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  138 |  return SEGTree[1].mx_tm;
      |         ~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:143:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  143 |  return SEGTree[1].mx_tm;
      |         ~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:148:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  148 |  return SEGTree[1].mx_tm;
      |         ~~~~~~~~~~~^~~~~

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