Submission #247679

#	Time	Username	Problem	Language	Result	Execution time	Memory
247679		fivefourthreeone	Horses (IOI15_horses)	C++17	0 / 100	265 ms	51064 KiB

horses

#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a); i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"debug"<<endl
 
using namespace std;
using ll = long long;
using ld = long double;
const ll MOD = 1e9+7;
const double PI = acos(-1);
const int INF = 0x3f3f3f3f;
const int NINF = 0x3f3f3f40;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0x3f3f3f3f3f3f3f40;
const int mxN = 500001;
int n;
set<int> good;
int startpos = -1;
int sgmax[2*mxN];
ll ans = 1;
ll x[mxN];
int y[mxN];
void build() {
    for(int i=n; i<2*n; ++i) sgmax[i] = y[i-n];
    for(int i=n-1; i>0; --i) sgmax[i] = max(sgmax[i<<1], sgmax[i<<1|1]);
}
void upd(int p, int val) {
    for(sgmax[p+=n] =val; p>0; p>>=1) sgmax[p>>1] = max(sgmax[p], sgmax[p^1]);
}
int qmax(int l, int r) {
    r++;
    int res = 0;
    for(l+=n, r+=n; l<r; l>>=1, r>>=1) {
        if(l&1)res = max(res, sgmax[l++]);
        if(r&1)res = max(res, sgmax[--r]);
    }
    return res;
}
ll binpow(ll a, ll b) { ll res = 1; while(b){ if(b&1) res = (res*a)%MOD; b>>=1; a = (a*a)%MOD;}return res;}
ll modInv(ll a) {return binpow(a, MOD-2);}
ll solve() {
    if(startpos==-1) return qmax(0, n-1);
    ll best= 1;
    ll curr = 1;
    ll partans = 1;
    int start = startpos+1;
    auto it = --good.end();
    while(partans<(ll)(1e9+7)&&start>startpos) {
        partans*=x[*it];
        start = *it;
        //cout<<partans<<" ";
        if(it==good.begin())break;
        it--;
    }
    //cout<<"\n";
    partans = 1;
    owo(i, startpos, start){
        partans = partans*x[i]%MOD;
    }
    //cout<<startpos<<" "<<start<<"\n";
    it = good.lower_bound(start);
    
    while(it!=good.end()) {
        curr = curr*(x[*it]);
        best = max(best, (ll)qmax(*it, next(it)==good.end() ? n-1 : *next(it))*curr);
        it++;
    }
    best%=MOD;
    //cout<<ans<<" "<<partans<<" "<<best<<"\n";
    return ((ans*partans)%MOD*best%MOD);
}
ll init(int N, int X[], int Y[]) {
    n = N;
    owo(i, 0, mxN) {
        x[i] = X[i];
        y[i] = Y[i];
    }
    build();
    owo(i, 0, n) {
        if(x[i]>1) good.insert(i);
    }
    auto it = --good.end();
    int num = 60;
    while(num) {
        num--;
        if(it==good.begin())break;
        it--;
    }
    startpos = *it;
    owo(i, 0, startpos) {
        ans = (ans*x[i])%MOD;
    }
    return solve();
}
ll updateX(int pos, int val) {
    if(x[pos]==1&&val!=1) {
        good.insert(pos);
        if(pos<startpos) {
            ans = (ans*val)%MOD;
        }else if(pos>startpos){
            if(startpos>-1) {
                ans = (ans*x[startpos]%MOD);
            }
            auto it = good.upper_bound(startpos);
            startpos = (it==good.end() ? -1 : *it);
        }
        //cout<<ans<<" "<<startpos<<"\n";
    }else if(x[pos]!=1&&val==1) {
        auto it = good.find(pos);
        if(pos<startpos) {
            ans = (ans*modInv(x[pos]))%MOD;
        }else if(pos>=startpos) {
            if(it!=good.begin()) {
                startpos = *prev(it);
            }
        }
        good.erase(good.find(pos));
    }else if(x[pos]!=1) {
        if(pos<startpos) {
            ans = (ans*modInv(x[pos]))%MOD;
            ans = (ans*val)%MOD;
        }
    }
    x[pos] = val;
    return solve();
}
ll updateY(int pos, int val) {
    upd(pos, val);
    return solve();
}
/*int main()
{
    //freopen("filename.in", "r", stdin);
    //freopen("filename.out", "w", stdout);
    cin.tie(0)->sync_with_stdio(0);
    ll ok = 1;
    int tempn;
    int tempx[mxN];
    int tempy[mxN];
    cin>>tempn;
    owo(i, 0, tempn) {
        cin>>tempx[i];
        ok = (ok*tempx[i])%MOD;
    }
    owo(i,0, tempn) {
        cin>>tempy[i];
    }
    ok = ok*3%MOD;
    cout<<ok<<"\n";
    cout<<init(tempn, tempx, tempy)<<"\n";
    int q;
    int a, b;
    cin>>q;
    while(q--) {
        cin>>a>>b;
        cout<<updateX(a, b)<<"\n";
    }
    return 0;
}*/

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