Submission #1243168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243168		moondarkside	Horses (IOI15_horses)	C++20	17 / 100	290 ms	134416 KiB

horses

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

#define MODULO (long long) 1000000007



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){
        New={(mult%MODULO)*left.inMult%MODULO,right.outMult,right.SellMult,over};
    }
    else{
        New={left.inMult,right.inMult*right.outMult*left.outMult,left.SellMult,left.inOver};
    }
    Segtree[n]=New;
    return Segtree[n];
}

int init(int N,int* X,int* 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;i++){
        struct Point temp={X[i],1,Y[i],false};
        update(temp,i,0,num,1);
    }
    return (Segtree[1].inMult*Segtree[1].SellMult)%MODULO;
}

int updateX(int pos,int 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;
}

int updateY(int pos,int 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: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23