Submission #485049

#	Time	Username	Problem	Language	Result	Execution time	Memory
485049		jeroenodb	Horses (IOI15_horses)	C++14	17 / 100	180 ms	62564 KiB

horses

#include "horses.h"
#include "bits/stdc++.h"
#ifdef LOCAL
#include "grader.cpp"
#endif
using namespace std;
#define all(x) begin(x),end(x)
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1;
const ll oo = 1e9+1;
const long long MD = 1e9+7;
template<long long MOD=MD> struct mdint {
    int d=0;
    mdint () {d=0;}
    mdint (long long _d) : d(_d%MOD){};
    friend mdint& operator+=(mdint& a, const mdint& o) {
        a.d+=o.d; if(a.d>=MOD) a.d-=MOD;
        return a;
    }
    friend mdint& operator-=(mdint& a, const mdint& o) {
        a.d-=o.d; if(a.d<0) a.d+=MOD;
        return a;
    }
    friend mdint& operator*=(mdint& a, const mdint& o) {
        return a = mdint((ll)a.d*o.d);
    }
    mdint operator*(const mdint& o) const {
        mdint res = *this;
        res*=o;
        return res;
    }
    mdint operator+(const mdint& o) const {
        mdint res = *this;
        res+=o;
        return res;
    }
    mdint operator-(const mdint& o) const {
        mdint res = *this;
        res-=o;
        return res;
    }
    mdint operator^(long long b) const {
        mdint tmp = 1;
        mdint power = *this;
        while(b) {
            if(b&1) {
                tmp = tmp*power;
            }
            power = power*power;
            b/=2;
        }
        return tmp;
    }
    friend mdint operator/=(mdint& a, const mdint& o) {
        a *= (o^(MOD-2));
        return a;
    }
    mdint operator/(const mdint& o) {
        mdint res = *this;
        res/=o;
        return res;
    }
    bool operator==(const mdint& o) { return d==o.d;}
    bool operator!=(const mdint& o) { return d!=o.d;}
    friend istream& operator>>(istream& c, mdint& a) {return c >> a.d;}
    friend ostream& operator<<(ostream& c, const mdint& a) {return c << a.d;}
};
using  mint = mdint<MD>;
struct node {
    mint prod=1;
    __int128 mx=0;
    int prodl=1;
    node() {
    }
    node(int x, int y) {
        mx = (ll)x*y;
        prod=x;
        prodl=x;
    }
    void merge(const node& o) {
        prod*=o.prod;
        mx = max(mx,o.mx*prodl);
        prodl = min(oo, (ll)prodl*o.prodl);
    }
    friend node merge(node a, const node& b) {
        a.merge(b);
        return a;
    }
};
struct segtree {
    int ptwo,n;
    vector<node> seg;
    segtree(){}
    node& operator[](int i) {
        return seg[i+ptwo];
    }
    segtree(int nn) {
        ptwo=1, n=nn;
        while(ptwo<n) ptwo*=2;
        seg.assign(ptwo*2,node(1,0));
    }
    auto query(int l, int r) {
        assert(l>=0 and l<ptwo and r >=0 and r<ptwo);
        l+=ptwo; r+=ptwo;
        node resl, resr;
        while(l and l<=r) {
            if(l%2==1) resl = merge(resl,seg[l++]);
            if(r%2==0) resr = merge(seg[r--],resr);
            l/=2; r/=2;
        }
        return merge(resl,resr);
    }
    auto cutoff() {
        if(seg[1].prodl<oo) return 0;
        int i=1;
        ll prod=1;
        while(i<ptwo) {
            if(seg[i*2+1].prodl*prod>=oo) {
                i=i*2+1;
            } else {
                prod = min(oo, prod*seg[i*2+1].prodl);
                i=i*2;
            }
        }
        return i-ptwo;
    }
    void update(int i, int x, int y) {
        assert(i>=0 and i<ptwo);
        i+=ptwo;
        seg[i] = node(x,y);
        for(i/=2;i>=1;i/=2) {
            seg[i] = merge(seg[2*i],seg[2*i+1]);
        }
    }
    mint best() {
        int i = cutoff();
        if(i==0) {
            return ll(query(0,n-1).mx % MD);
        }
        return query(0,i-1).prod * ll( query(i,n-1).mx % MD);
    }
    void build() {
        for(int i=ptwo-1;i>=1;--i) {
            seg[i] = merge(seg[2*i],seg[2*i+1]);
        }
    }
};
segtree seg;
int *x, *y;
int init(int N, int X[], int Y[]) {
    x=X,y=Y;
    seg = segtree(N);
    for(auto i=0;i<N;++i) {
        seg[i] = node(X[i],Y[i]);
    }
    seg.build();
    return seg.best().d;
}

int updateX(int pos, int val) {	
    x[pos]=val;
    seg.update(pos,x[pos],y[pos]);
    return seg.best().d;
}

int updateY(int pos, int val) {
	y[pos] = val;
    seg.update(pos,x[pos],y[pos]);
    return seg.best().d;
}

Compilation message (stderr)

horses.cpp: In member function 'void node::merge(const node&)':
horses.cpp:86:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   86 |         prodl = min(oo, (ll)prodl*o.prodl);
      |                 ~~~^~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In instantiation of 'mdint<MOD>::mdint(long long int) [with long long int MOD = 1000000007]':
horses.cpp:73:15:   required from here
horses.cpp:18:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   18 |     mdint (long long _d) : d(_d%MOD){};
      |                              ~~^~~~

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