제출 #1247798

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247798		vtnoo	말 (IOI15_horses)	C++20	20 / 100	573 ms	53012 KiB

horses

#pragma once

#include <bits/stdc++.h>

using namespace std;

const int mod=1e9+7, MAXN=500005;
long long a[MAXN], b[MAXN];
int n;

struct Node{
    long long prod, rmq;
};

Node st[2<<20];
set<long long> h;

void build(int v, int s, int e){
    if(s==e){
        st[v].prod=a[s];
        st[v].rmq=b[s];
        return;
    }
    int m=(s+e)/2;
    build(v*2, s, m);
    build(v*2+1, m+1, e);
    st[v].prod=(st[v*2].prod*st[v*2+1].prod)%mod;
    st[v].rmq=max(st[v*2].rmq, st[v*2+1].rmq);
    return;
}

void upd(int v, int s, int e, const int ts, const int te, Node xx){
    if(e<ts||s>te){
        return;
    }else if(ts<=s&&e<=te){
        if(xx.rmq==-1){
            st[v].prod=xx.prod;
        }else st[v].rmq=xx.rmq;
        return; 
    }
    int m=(s+e)/2;
    upd(v*2, s, m, ts, te, xx);
    upd(v*2+1, m+1, e, ts, te, xx);
    st[v].prod=(st[v*2].prod*st[v*2+1].prod)%mod;
    st[v].rmq=max(st[v*2].rmq, st[v*2+1].rmq);
}

long long que(int v, int s, int e, const int ts, const int te, bool type){
    if(e<ts||s>te){
        if(type==0){
            return 1;
        }else return 0;
    }else if(ts<=s&&e<=te){
        if(type==0){
            return st[v].prod%mod;
        }else return st[v].rmq;
    }
    int m=(s+e)/2;
    if(type==0){
        return (que(v*2, s, m, ts, te, type)*que(v*2+1, m+1, e, ts, te, type))%mod;
    }else return max(que(v*2, s, m, ts, te, type), que(v*2+1, m+1, e, ts, te, type));
}

int calc(){
    int j, count=0;
    long long prod=1, last_y;
    vector<int> indices;
    for(auto it=h.rbegin(); it!=h.rend()&&count<31; it++, count++){
        indices.push_back(*it);
    }
    reverse(indices.begin(), indices.end());
    indices.push_back(n);
	j=*indices.begin();
	last_y=b[*indices.begin()];
	for(int i=0;i<(int)indices.size()-1;i++){
		prod*=a[indices[i]];
        if(last_y<prod*b[indices[i]]){
            last_y=b[indices[i]];
            prod=1;
            j=indices[i];
        }
        long long cur_y=que(1, 0, n-1, indices[i]+1, indices[i+1]-1, 1);
        if(last_y<prod*cur_y){
            last_y=cur_y;
            prod=1;
            j=indices[i];
        }
    }
    return (que(1, 0, n-1, 0, j, 0)*last_y)%mod;
}

int init(int N, int X[], int Y[]){
    n=N;
    for(int i=0;i<n;i++){
       a[i]=X[i];
        if(a[i]>=2){
            h.insert(i);
        }
        b[i]=Y[i];
    }
    build(1, 0, n-1);
    //~ cout<<"ARR: ";
    //~ for(int i=0;i<n;i++){
		//~ cout<<que(1,0,n-1,i,i,1)<<" ";
	//~ }
	//~ cout<<endl;
    //~ cout<<"MAX: "<<que(1,0,n-1,0,n-1,1)<<endl;
    return calc();
}

int updateX(int pos, int val){
    h.erase(pos);
    a[pos]=val;
    if(val>=2){
        h.insert(pos);
    }
    upd(1,0,n-1,pos,pos,Node{val,-1});
    return calc();
}

int updateY(int pos, int val){
    b[pos]=val;
    upd(1,0,n-1,pos,pos,Node{-1,val});
    return calc();
}

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

horses.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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