제출 #1030280

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1030280		pcc	말 (IOI15_horses)	C++17	57 / 100	1570 ms	47444 KiB

horses

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

#define ll long long
#define pll pair<ll,ll>
#define fs first
#define sc second
const ll mod = 1e9+7;
const ll mxn = 5e5+10;

int N;
int arr[mxn],brr[mxn];
set<int> st;

struct SEG{
#define ls now*2+1
#define rs now*2+2
#define mid ((l+r)>>1)
	int mx[mxn*4];
	ll seg[mxn*4];
	void build(int now,int l,int r){
		if(l == r){
			seg[now] = arr[l];
			mx[now] = brr[l];
			return;
		}
		build(ls,l,mid);
		build(rs,mid+1,r);
		mx[now] = max(mx[ls],mx[rs]);
		seg[now] = seg[ls]*seg[rs];
		if(seg[now]>=mod)seg[now] = mod+seg[now]%mod;
		return;
	}
	void modify(int now,int l,int r,int p){
		if(l == r){
			seg[now] = arr[l];
			mx[now] = brr[l];
			return;
		}
		if(mid>=p)modify(ls,l,mid,p);
		else modify(rs,mid+1,r,p);
		mx[now] = max(mx[ls],mx[rs]);
		seg[now] = seg[ls]*seg[rs];
		if(seg[now]>=mod)seg[now] = mod+seg[now]%mod;
	}
	ll getsum(int now,int l,int r,int s,int e){
		if(l>=s&&e>=r)return seg[now];
		if(mid>=e)return getsum(ls,l,mid,s,e);
		else if(mid<s)return getsum(rs,mid+1,r,s,e);
		else{
			auto re = getsum(ls,l,mid,s,e)*getsum(rs,mid+1,r,s,e);
			if(re>=mod)return mod+re%mod;
			else return re;
		}
	}
	ll getmax(int now,int l,int r,int s,int e){
		if(l>=s&&e>=r)return mx[now];
		if(mid>=e)return getmax(ls,l,mid,s,e);
		else if(mid<s)return getmax(rs,mid+1,r,s,e);
		else return max(getmax(ls,l,mid,s,e),getmax(rs,mid+1,r,s,e));
	}
#undef ls
#undef rs
#undef mid
};

SEG seg;

bool cmp(int a,int b){
	if(a>b)return seg.getmax(0,0,N-1,a,N-1)*seg.getsum(0,0,N-1,b+1,a)<seg.getmax(0,0,N-1,b,N-1);
	else return seg.getmax(0,0,N-1,a,N-1)<seg.getmax(0,0,N-1,b,N-1)*seg.getsum(0,0,N-1,a+1,b);
}

ll getans(){
	st.insert(0);
	vector<int> v;
	ll pref = 1;
	for(auto it = st.rbegin();it != st.rend()&&pref<mod;it++){
		v.push_back(*it);
		pref *= arr[*it];
	}
	sort(v.begin(),v.end(),cmp);
	assert(v.size()<=32);
	int tar = v.back();
	return seg.getmax(0,0,N-1,tar,N-1)*seg.getsum(0,0,N-1,0,tar)%mod;
}

int init(int NN, int X[], int Y[]) {
	N = NN;
	for(int i = 0;i<N;i++){
		arr[i] = X[i];
		if(arr[i] != 1)st.insert(i);
		brr[i] = Y[i];
	}
	seg.build(0,0,N-1);
	//cerr<<"INIT! "<<seg.getmax(0,0,N-1,0,N-1)<<endl;
	return getans();
}

int updateX(int pos, int val) {	
	arr[pos] = val;
	if(arr[pos] != 1)st.insert(pos);
	else if(arr[pos] == 1&&st.find(pos) != st.end())st.erase(pos);
	seg.modify(0,0,N-1,pos);
	return getans();
}

int updateY(int pos, int val) {
	brr[pos] = val;
	seg.modify(0,0,N-1,pos);
	return getans();
}

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

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:98:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   98 |  return getans();
      |         ~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:106:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  106 |  return getans();
      |         ~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:112:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  112 |  return getans();
      |         ~~~~~~^~

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