제출 #1013657

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1013657		Mardonbekhazratov	말 (IOI15_horses)	C++17	100 / 100	320 ms	48520 KiB

horses

#include "horses.h"
#include<algorithm>
#include<vector>
#include<iostream>
#include<set>
const long long INFLL=1e18;
const int INF=1e9;
const int MOD=1e9+7;

using namespace std;

struct SegTree{
    int N;
    const int NEU=0;
    vector<int>tree;

    int merge(int a,int b){
        return max(a,b);
    }

    void build(vector<int>&a){
        N=1;
        int n=a.size();
        while(N<n) N<<=1;

        tree.assign(N<<1,NEU);
        for(int i=0;i<n;i++) tree[i+N]=a[i];
        for(int i=N-1;i>0;i--) tree[i]=merge(tree[i<<1],tree[i<<1|1]);
    }

    void update(int v,int l,int r,int id,int x){
        if(l>id || id>=r) return;
        if(r-l==1){
            tree[v]=x;
            return;
        }

        int mid=(l+r)>>1;
        update(v<<1,l,mid,id,x);
        update(v<<1|1,mid,r,id,x);

        tree[v]=merge(tree[v<<1],tree[v<<1|1]);
    }

    void update(int id,int x){
        return update(1,0,N,id,x);
    }

    int get(int v,int l,int r,int ql,int qr){
        if(l>=qr || ql>=r) return NEU;
        if(l>=ql && qr>=r) return tree[v];

        int mid=(l+r)>>1;
        int a=get(v<<1,l,mid,ql,qr);
        int b=get(v<<1|1,mid,r,ql,qr);
        return merge(a,b);
    }

    int get(int l,int r){
		if(r<=l) return 0;
        return get(1,0,N,l,r);
    }
};

int inv(int x){
	return x>1 ? MOD-(long long)(MOD/x)*inv(MOD%x)%MOD : x;
}

int n;
vector<int>x,y;
set<int>p;

SegTree S;
long long pref;

int get(){
	long long ans=1;
	long long pr=pref;
	int last=n;
	for(int j:p){
		int i=n-j;
		ans=max(ans,1LL*S.get(i,last));
		last=i;
		if(ans>=INF){
			ans%=MOD;
			return pr*ans%MOD;
		}
		ans*=x[i];
		pr=pr*inv(x[i])%MOD;
	}
	return max(ans*pr,1LL*S.get(0,last))%MOD;
}

int init(int N, int X[], int Y[]) {
	n=N;
	pref=1;
	x.resize(n);
	y.resize(n);
	for(int i=0;i<n;i++){
		x[i]=X[i],y[i]=Y[i];
		pref=pref*x[i]%MOD;
		if(x[i]>1) p.insert(n-i);
	}
	S.build(y);
	return get();
}


int updateX(int pos, int val) {	
	if(x[pos]>1) p.erase(n-pos);
	pref=pref*inv(x[pos])%MOD*val%MOD;
	x[pos]=val;
	if(x[pos]>1) p.insert(n-pos);
	return get();
}

int updateY(int pos, int val) {
	S.update(pos,val);
	return get();
}

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

horses.cpp: In member function 'void SegTree::build(std::vector<int>&)':
horses.cpp:23:21: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   23 |         int n=a.size();
      |               ~~~~~~^~
horses.cpp: In function 'int inv(int)':
horses.cpp:66:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   66 |  return x>1 ? MOD-(long long)(MOD/x)*inv(MOD%x)%MOD : x;
      |         ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int get()':
horses.cpp:86:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   86 |    return pr*ans%MOD;
      |           ~~~~~~^~~~
horses.cpp:91:38: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   91 |  return max(ans*pr,1LL*S.get(0,last))%MOD;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

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