제출 #571895

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
571895		CSQ31	Horses (IOI15_horses)	C++17	100 / 100	792 ms	52308 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define sz(v) (int)(v.size())
const int MAXN = 5e5+5,MOD = 1e9+7;
ll x[MAXN],y[MAXN],bit[MAXN];
int n;
int binpow(int n,int k){
	int res = 1;
	while(k){
		if(k&1)res = res * 1LL *n%MOD;
		n = n*1LL*n%MOD;
		k/=2;
	}
	return res;
}
void upd(int i,int val){
	int j = i;
	int c = binpow(x[i],MOD-2) * 1LL * val%MOD;
	for(;i<=n;i+=i&(-i))bit[i] = bit[i] * 1LL *c %MOD;
	x[j] = val;
}
int query(int i){
	int res = 1;
	for(;i>0;i-=i&(-i))res = res * 1LL * bit[i]%MOD;
	return res;
}
int t[4*MAXN];
set<int,greater<int>>pip;
void upd(int v,int l,int r,int pos,int x){
	if(l==r){
		t[v] = x;
		return;
	}
	int tm = (l+r)/2;
	if(pos<=tm)upd(2*v,l,tm,pos,x);
	else upd(2*v+1,tm+1,r,pos,x);
	t[v] = max(t[2*v],t[2*v+1]);
}
int query(int v,int l,int r,int tl,int tr){
	if(l>r)return 0;
	if(l==tl && r==tr)return t[v];
	int tm = (tl+tr)/2;
	int a = query(2*v,l,min(r,tm),tl,tm);
	int b = query(2*v+1,max(tm+1,l),r,tm+1,tr);
	return max(a,b);
}
void build(int v,int l,int r){
	if(l==r)t[v] = y[l];
	else{
		int tm = (l+r)/2;
		build(2*v,l,tm);
		build(2*v+1,tm+1,r);
		t[v] = max(t[2*v],t[2*v+1]);
	}
	
}
ll smort(){
	vector<int>v;
	for(int x:pip){
		if(sz(v)>30)break;
		v.push_back(x);
	}
	if(v.empty())return t[1];
	if(sz(v)<=30 && v.back() != 1)v.push_back(1);
	reverse(v.begin(),v.end());
	v.push_back(n+1);
	int m = sz(v);
	vector<ll>Y(m,0);
    for(int i=0;i<m-1;i++)Y[i] = query(1,v[i],v[i+1]-1,1,n);
	int last = 0;
	ll cur = 1;
	for(int i=1;i+1<m;i++){
		cur*=x[v[i]];
		if(cur > Y[last]){
			cur = 1;
			last = i;
			continue;
		} 
		if(cur * Y[i] > Y[last]){
			cur = 1;
			last = i;
		}
	}
	ll ans = query(v[last]);
	ans = ans*Y[last]%MOD;
	return ans;	
}
int init(int N, int X[], int Y[]) {
	n = N;
	for(int i=1;i<=n;i++){
		x[i] = X[i-1];
		y[i] = Y[i-1];
	}
	for(int i=1;i<=n;i++)bit[i] = 1;
	for(int i=1;i<=n;i++){
		int tmp = x[i];
		x[i] = 1;
		upd(i,tmp);
		if(x[i]>1)pip.insert(i);
	}
	build(1,1,n);
	return smort();
}

int updateX(int pos, int val) {	
	pos++;
	upd(pos,val);
	if(val > 1)pip.insert(pos);
	else if(pip.count(pos))pip.erase(pos);
	return smort();
}

int updateY(int pos, int val) {
	pos++;
	y[pos] = val;
	upd(1,1,n,pos,val);
	return smort();
}

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

horses.cpp: In function 'int binpow(int, int)':
horses.cpp:9:16: warning: declaration of 'n' shadows a global declaration [-Wshadow]
    9 | int binpow(int n,int k){
      |            ~~~~^
horses.cpp:8:5: note: shadowed declaration is here
    8 | int n;
      |     ^
horses.cpp:12:28: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   12 |   if(k&1)res = res * 1LL *n%MOD;
      |                ~~~~~~~~~~~~^~~~
horses.cpp:13:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   13 |   n = n*1LL*n%MOD;
      |       ~~~~~~~^~~~
horses.cpp: In function 'void upd(int, int)':
horses.cpp:20:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   20 |  int c = binpow(x[i],MOD-2) * 1LL * val%MOD;
      |                 ~~~^
horses.cpp:20:40: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   20 |  int c = binpow(x[i],MOD-2) * 1LL * val%MOD;
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int query(int)':
horses.cpp:26:45: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   26 |  for(;i>0;i-=i&(-i))res = res * 1LL * bit[i]%MOD;
      |                           ~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'void upd(int, int, int, int, int)':
horses.cpp:31:40: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   31 | void upd(int v,int l,int r,int pos,int x){
      |                                    ~~~~^
horses.cpp:7:4: note: shadowed declaration is here
    7 | ll x[MAXN],y[MAXN],bit[MAXN];
      |    ^
horses.cpp: In function 'void build(int, int, int)':
horses.cpp:50:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   50 |  if(l==r)t[v] = y[l];
      |                 ~~~^
horses.cpp: In function 'll smort()':
horses.cpp:61:10: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   61 |  for(int x:pip){
      |          ^
horses.cpp:7:4: note: shadowed declaration is here
    7 | ll x[MAXN],y[MAXN],bit[MAXN];
      |    ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:98:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   98 |   int tmp = x[i];
      |             ~~~^
horses.cpp:104:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  104 |  return smort();
      |         ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:112:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  112 |  return smort();
      |         ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:119:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  119 |  return smort();
      |         ~~~~~^~

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