Submission #1243183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243183		moondarkside	Horses (IOI15_horses)	C++20	100 / 100	370 ms	138544 KiB

horses

#include<bits/stdc++.h>
using namespace std;

#define MODULO (long long) 1000000007

#define int long long

struct Point{
    long long inMult;
    long long outMult;
    long long SellMult;
    bool inOver;
};

vector<struct Point> Segtree;

int num;
vector<int> Yg;
vector<int> Xg;

struct Point update(struct Point cr,int pos,int l,int r,int n){
    if(r<pos){
        return Segtree[n];
    }
    
    if(pos<l){
        return Segtree[n];
    }
    if(r==l && l==pos){
        Segtree[n]=cr;
        return Segtree[n];
    }
    
    struct Point left=update(cr,pos,l,(l+r)/2,2*n);
    struct Point right=update(cr,pos,(l+r)/2+1,r,2*n+1);
    long long mult=left.outMult*right.inMult;
    bool over= ((mult>=MODULO) || right.inOver);
    
    struct Point New;
    
    if(over || mult*right.SellMult>=left.SellMult){
        if(mult*left.inMult>MODULO){
            over=true;
        }
        New={((mult%MODULO)*left.inMult)%MODULO,right.outMult,right.SellMult,over};
    }
    else{
        if(right.inMult*right.outMult*left.outMult>MODULO){
            while(true){
                cout<<"YES";
            }
        }
        New={left.inMult,right.inMult*right.outMult*left.outMult,left.SellMult,left.inOver};
    }
    Segtree[n]=New;
    return Segtree[n];
}

signed init(signed N,signed* X,signed* Y){
    for(int i=0;i<N;i++){
        Xg.push_back(X[i]);
        Yg.push_back(Y[i]);
    }
    Segtree=vector<struct Point>(N*8);
    num=N-1;
    for(int i=0;i<N-1;i++){
        struct Point temp={X[i],1,Y[i],false};
         update(temp,i,0,num,1);  
    }
    struct Point temp={X[N-1],1,Y[N-1],false};
    update(temp,N-1,0,num,1);
    return (Segtree[1].inMult*Segtree[1].SellMult)%MODULO;
}

signed updateX(signed pos,signed val){
    Xg[pos]=val;
    struct Point temp={val,1,Yg[pos],false};
    update(temp,pos,0,num,1);
    return (Segtree[1].inMult*Segtree[1].SellMult)%MODULO;
}

signed updateY(signed pos,signed val){
    Yg[pos]=val;
    struct Point temp={Xg[pos],1,val,false};
    update(temp,pos,0,num,1);
    return (Segtree[1].inMult*Segtree[1].SellMult)%MODULO;
}

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