Submission #1247690

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247690		vtnoo	Horses (IOI15_horses)	C++20	0 / 100	466 ms	52240 KiB

horses

#pragma once

#include <bits/stdc++.h>

using namespace std;

const int mod=1e9+7, MAXN=500005;
long long X[MAXN], Y[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=X[v];
        st[v].rmq=Y[v];
        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 x){
    if(e<ts||s>te){
        return;
    }else if(ts<=s&&e<=te){
        if(x.rmq==-1){
            st[v].prod=x.prod;
        }else st[v].rmq=x.rmq;
        return; 
    }
    int m=(s+e)/2;
    upd(v*2, s, m, ts, te, x);
    upd(v*2+1, m+1, e, ts, te, x);
    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;
        }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=max(0, n-31), count=0;
    long long prod=1, last_y=Y[j];
    vector<int> indices;
    for(auto it=h.rbegin(); it!=h.rend()&&count<30; it++, count++){
        indices.push_back(*it);
    }
    reverse(indices.begin(), indices.end());
    indices.push_back(n);
    for(int i=0;i<(int)indices.size()-1;i++){
        if(last_y<prod*Y[i]){
            last_y=Y[i];
            prod=1;
            j=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=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++){
        X[i]=x[i];
        if(x[i]>=2){
            h.insert(i);
        }
        Y[i]=y[i];
    }
    build(1, 0, n-1);
    return calc();
}

int updateX(int pos, int val){
    h.erase(pos);
    X[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){
    Y[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: 0 / 17
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23