Submission #349049

#	Time	Username	Problem	Language	Result	Execution time	Memory
349049		qwerasdfzxcl	Horses (IOI15_horses)	C++14	Compilation error	0 ms	0 KiB

horses

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
struct l3{
    ll r;
    bool inf;
    l3(){}
    l3(ll _r, bool _inf){r=_r, inf=_inf;}
};
struct node{
    int idx;
    ll pre, all;
    l3 pl, sl, al;
    node(){}
    node(int _idx, ll _pre, ll _all, l3 _pl, l3 _sl, l3 _al){
        idx=_idx, pre=_pre, all=_all, pl=_pl, sl=_sl, al=_al;
    }
};
node tree[2002000];
ll x[500500], y[500500], mod=1e9+7;
int n;

ll pw(ll a, ll b){
    if (!b) return 1;
    ll tmp=pw(a, b/2);
    tmp=(tmp*tmp)%mod;
    if (b&1) tmp=(tmp*a)%mod;
    return tmp;
}

ll rev(ll a){
    return pw(a, mod-2);
}

l3 mul(l3 a, l3 b){
    l3 ret;
    if (a.inf || b.inf) return l3(0, 1);
    if (a.r*b.r>=mod) return l3(0, 1);
    ret=l3(a.r*b.r, 0);
    return ret;
}

node combine(node &a, node &b){
    if (a.idx==-2) return b;
    if (b.idx==-2) return a;
    node ret;
    ret.all=(a.all*b.all)%mod;
    ret.al=mul(a.al, b.al);
    l3 chk=mul(mul(a.sl, b.pl), l3(y[b.idx], 0));
    if (chk.inf || chk.r>=y[a.idx]){
        ret.idx=b.idx;
        ret.pre=(a.all*b.pre)%mod;
        ret.pl=mul(a.al, b.pl);
        ret.sl=b.sl;
        return ret;
    }
    ret.idx=a.idx;
    ret.pre=a.pre;
    ret.pl=a.pl;
    ret.sl=mul(a.sl, b.al);
    return ret;
}

void build(){
    for (int i=n-1;i>0;i--) tree[i]=combine(tree[i<<1], tree[i<<1|1]);
}

void update(int i, node val){
    for (tree[i += n]=val;i >>= 1;) tree[i]=combine(tree[i<<1], tree[i<<1|1]);
}

node query(int l, int r){
    node resl=node(-2, 1, 1, l3(1, 0), l3(1, 0), l3(1, 0)), resr=node(-2, 1, 1, l3(1, 0), l3(1, 0), l3(1, 0));
    for (l += n, r += n;l<r;l>>=1, r>>=1){
        if (l&1) resl=combine(resl, tree[l++]);
        if (r&1) resr=combine(tree[--r], resr);
    }
    return combine(resl, resr);
}

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int m;
    y[0]=1;
    cin >> n;
    for (int i=1;i<=n;i++) cin >> x[i];
    for (int i=1;i<=n;i++) cin >> y[i];
    for (int i=0;i<n;i++){
        ll tmp=(((x[i+1]*y[i+1])%mod)*rev(y[i]))%mod;
        tree[n+i].all=tmp;
        tree[n+i].al=l3(x[i+1], 0);
        if (x[i+1]*y[i+1]>=y[i]){
            tree[n+i].idx=i+1;
            tree[n+i].pre=tmp;
            tree[n+i].pl=l3(x[i+1], 0);
            tree[n+i].sl=l3(1, 0);
        }
        else{
            tree[n+i].idx=i;
            tree[n+i].pre=1;
            tree[n+i].pl=l3(1, 0);
            tree[n+i].sl=l3(x[i+1], 0);
        }
    }
    build();
    cout << query(0, n).pre << '\n';
    cin >> m;
    while(m--){
        int tp, pos;
        ll val0;
        cin >> tp >> pos >> val0;
        if (tp==1){
            node val=tree[pos+n];
            ll tmp=(rev(x[pos+1])*val0)%mod;
            val.all=(val.all*tmp)%mod;
            val.al=l3(val0, 0);
            if (val.idx!=pos+1) val.sl=l3(val0, 0);
            else{
                val.pre=val.all;
                val.pl=l3(val0, 0);
            }
            x[pos+1]=val0;
            update(pos, val);
            cout << query(0, n).pre << '\n';
        }
        else{
            node val1=tree[pos+n], val2=tree[pos+1+n];
            ll tmp1=(rev(y[pos+1])*val0)%mod;
            ll tmp2=rev(tmp1);

            val1.all=(val1.all*tmp1);
            if (val1.idx==pos+1) val1.pre=val1.all;
            y[pos+1]=val0;
            update(pos, val1);

            if(pos!=n-1){
                val2.all=(val2.all*tmp2)%mod;
                if (val2.idx==pos+2) val2.pre=val2.all;
                update(pos+1, val2);
            }
            cout << query(0, n).pre << '\n';
        }
    }
    return 0;
}

Compilation message (stderr)

/tmp/ccagRn3t.o: In function `main':
grader.c:(.text.startup+0x0): multiple definition of `main'
/tmp/ccQbriKo.o:horses.cpp:(.text.startup+0x0): first defined here
/tmp/ccagRn3t.o: In function `main':
grader.c:(.text.startup+0x360): undefined reference to `init(int, int*, int*)'
grader.c:(.text.startup+0x903): undefined reference to `updateX(int, int)'
grader.c:(.text.startup+0x97f): undefined reference to `updateY(int, int)'
collect2: error: ld returned 1 exit status