제출 #1018656

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1018656		amirhoseinfar1385	말 (IOI15_horses)	C++17	100 / 100	1373 ms	60576 KiB

horses

#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=500000+10,mod=1e9+7,lg=19,kaf=(1<<(lg));
int allx[maxn],ally[maxn],n;
set<int>st;
struct segment{
	struct node{
		int maxa,zarb;
		node(){
			maxa=0;
			zarb=1;
		}
	};
	node seg[(1<<(lg+1))];
	void upd(int i,int w){
		i+=kaf;
		seg[i].zarb=seg[i].maxa=w;
		i>>=1;
		while(i>0){
			seg[i].maxa=max(seg[(i<<1)].maxa,seg[(i<<1)^1].maxa);
			seg[i].zarb=1ll*seg[(i<<1)].zarb*seg[(i<<1)^1].zarb%mod;
			i>>=1;
		}
	}
	int porszarb(int i,int l,int r,int tl,int tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return 1;
		}
		if(l>=tl&&r<=tr){
			return seg[i].zarb;
		}
		int m=(l+r)>>1;
		return 1ll*porszarb((i<<1),l,m,tl,tr)*porszarb((i<<1)^1,m+1,r,tl,tr)%mod;
	}
	int porsmx(int i,int l,int r,int tl,int tr){
		int ret=0;
		tl+=kaf;
		ret=max(ret,seg[tl].maxa);
		while(tl>1){
			if(tl&1){
				tl>>=1;
			}else{
				ret=max(ret,seg[tl^1].maxa);
				tl>>=1;
			}
		}
		return ret;
	}
}segx,segy;
int calc(){
	long long unnow=1;
	vector<int>ind;
	while((int)st.size()>0){
		unnow*=allx[(*st.rbegin())];
		ind.push_back((*st.rbegin()));
		st.erase((*st.rbegin()));
		if(unnow>1000000000){
			break;
		}
	}
	unnow/=allx[ind.back()];
	long long mx=0;
	for(int i=0;i<(int)ind.size();i++){
		mx=max(mx,unnow*segy.porsmx(1,0,kaf-1,ind[i],n));
		unnow/=allx[ind[i]];
	}
	mx%=mod;
	mx*=segx.porszarb(1,0,kaf-1,0,ind.back());
	mx%=mod;
	for(auto x:ind){
		st.insert(x);
	}
	return mx;
}

int init(int N, int X[], int Y[]) {
	n=N;
	allx[0]=1;
	st.insert(0);
	for(int i=1;i<=n;i++){
		//cout<<i<<endl;
		allx[i]=X[i-1];
		segx.upd(i,allx[i]);
		ally[i]=Y[i-1];
		segy.upd(i,ally[i]);
		if(allx[i]>1){
			st.insert(i);
		}
	}
	return calc();
}

int updateX(int pos, int val) {
	pos++;	
	allx[pos]=val;
	if(allx[pos]==1){
		st.erase(pos);
	}else{
		st.insert(pos);
	}
	segx.upd(pos,val);
	return calc();
}

int updateY(int pos, int val) {
	pos++;
	ally[pos]=val;
	segy.upd(pos,val);
	return calc();
}

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

horses.cpp: In member function 'void segment::upd(int, int)':
horses.cpp:22:55: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   22 |    seg[i].zarb=1ll*seg[(i<<1)].zarb*seg[(i<<1)^1].zarb%mod;
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In member function 'int segment::porszarb(int, int, int, int, int)':
horses.cpp:34:71: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   34 |   return 1ll*porszarb((i<<1),l,m,tl,tr)*porszarb((i<<1)^1,m+1,r,tl,tr)%mod;
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In member function 'int segment::porsmx(int, int, int, int, int)':
horses.cpp:36:17: warning: unused parameter 'i' [-Wunused-parameter]
   36 |  int porsmx(int i,int l,int r,int tl,int tr){
      |             ~~~~^
horses.cpp:36:23: warning: unused parameter 'l' [-Wunused-parameter]
   36 |  int porsmx(int i,int l,int r,int tl,int tr){
      |                   ~~~~^
horses.cpp:36:29: warning: unused parameter 'r' [-Wunused-parameter]
   36 |  int porsmx(int i,int l,int r,int tl,int tr){
      |                         ~~~~^
horses.cpp:36:42: warning: unused parameter 'tr' [-Wunused-parameter]
   36 |  int porsmx(int i,int l,int r,int tl,int tr){
      |                                      ~~~~^~
horses.cpp: In function 'int calc()':
horses.cpp:74:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   74 |  return mx;
      |         ^~

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