제출 #1098299

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1098299		alexander707070	Horses (IOI15_horses)	C++14	100 / 100	860 ms	49488 KiB

horses

#include<bits/stdc++.h>
#include "horses.h"

#define MAXN 500007
using namespace std;

const long long mod=1e9+7;

struct ST{
    int tree[4*MAXN];
    long long mult[4*MAXN];

    void update(int v,int l,int r,int pos,int val){
        if(l==r){
            tree[v]=val;
            mult[v]=val;
        }else{
            int tt=(l+r)/2;
            if(pos<=tt)update(2*v,l,tt,pos,val);
            else update(2*v+1,tt+1,r,pos,val);

            tree[v]=max(tree[2*v],tree[2*v+1]);
            mult[v]=(mult[2*v]*mult[2*v+1])%mod;
        }
    }

    int getmax(int v,int l,int r,int ll,int rr){
        if(ll>rr)return 0;
        if(l==ll and r==rr){
            return tree[v];
        }else{
            int tt=(l+r)/2;
            return max( getmax(2*v,l,tt,ll,min(tt,rr)) , getmax(2*v+1,tt+1,r,max(tt+1,ll),rr) );
        }
    }

    int solve(int v,int l,int r){
        if(l==r)return l;
        int tt=(l+r)/2;

        if(tree[2*v+1]>1)return solve(2*v+1,tt+1,r);
        return solve(2*v,l,tt);
    }

    int findpos(int v,int l,int r,int ll,int rr){
        if(ll>rr)return 0;
        if(l==ll and r==rr){
            if(tree[v]>1)return solve(v,l,r);
            return 0;
        }else{
            int tt=(l+r)/2;

            int curr=findpos(2*v+1,tt+1,r,max(tt+1,ll),rr);
            if(curr!=0)return curr;

            return findpos(2*v,l,tt,ll,min(tt,rr));
        }
    }

    long long getmult(int v,int l,int r,int ll,int rr){
        if(ll>rr)return 1;
        if(l==ll and r==rr)return mult[v];

        int tt=(l+r)/2;
        return (getmult(2*v,l,tt,ll,min(tt,rr)) * getmult(2*v+1,tt+1,r,max(tt+1,ll),rr))%mod;
    }
}xs,ys;

int n;
long long x[MAXN],y[MAXN];

int calc(){
    
    long long mult=1,res=0,ans=0;
    int to=n+1;

    vector< pair<int,int> > w;

    while(to>1 and mult<mod){
        int s=xs.findpos(1,1,n,1,to-1);
        if(s==0){
            w.push_back({1,to-1}); break;
        }else{
            w.push_back({s,to-1}); to=s;
            mult*=x[s];
        }
    }

    mult=1;
    for(int i=w.size()-1;i>=0;i--){
        long long curr=(long long) mult*ys.getmax(1,1,n,w[i].first,w[i].second);

        if(curr>res){
            res=curr;
            ans=((res%mod)*xs.getmult(1,1,n,1,w.back().first))%mod;
        }

        if(i>0)mult*=x[w[i-1].first];
    }

    return ans;
}

int init(int N, int X[], int Y[]) {
//int init(int N, vector<int> X, vector<int> Y) {

	n=N;
    for(int i=1;i<=n;i++){
        x[i]=X[i-1]; y[i]=Y[i-1];

        xs.update(1,1,n,i,x[i]);
        ys.update(1,1,n,i,y[i]);
    }

    return calc();
}

int updateX(int pos, int val) {	
	x[pos+1]=val;
    xs.update(1,1,n,pos+1,val);

    return calc();
}

int updateY(int pos, int val) {
	y[pos+1]=val;
    ys.update(1,1,n,pos+1,val);

    return calc();
}

/*int main(){

    init(3,{2,1,3},{3,4,1});
    cout<<updateY(1,2)<<"\n";

    return 0;
}*/

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

horses.cpp: In function 'int calc()':
horses.cpp:90:23: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   90 |     for(int i=w.size()-1;i>=0;i--){
      |               ~~~~~~~~^~
horses.cpp:101:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  101 |     return ans;
      |            ^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:111:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  111 |         xs.update(1,1,n,i,x[i]);
      |                           ~~~^
horses.cpp:112:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  112 |         ys.update(1,1,n,i,y[i]);
      |                           ~~~^

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