Submission #1247820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247820		vtnoo	Horses (IOI15_horses)	C++20	100 / 100	592 ms	53232 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, const 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=0, count=0;
    long long prod=1, last_y=0;
    vector<int> indices;
    for(auto it=h.rbegin(); it!=h.rend()&&count<33; it++, count++){
        indices.push_back(*it);
    }
    reverse(indices.begin(), indices.end());
    indices.push_back(n);
    if((int)indices.size()>1){
		j=*indices.begin();
		last_y=b[*indices.begin()];
	}
	indices.insert(indices.begin(), -1);
	for(int i=0;i<(int)indices.size()-1;i++){
		if(i!=0){
			prod*=a[indices[i]];
			if(last_y<prod*b[indices[i]]){
				last_y=b[indices[i]];
				prod=1;
				j=indices[i];
			}
		}
        if(indices[i]+1>indices[i+1]-1)continue;
        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();
}

Compilation message (stderr)

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

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