Submission #31205

#	Time	Username	Problem	Language	Result	Execution time	Memory
31205		cscandkswon	Horses (IOI15_horses)	C++14	100 / 100	886 ms	41156 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=500005;
const long long MOD=(1e9)+7;

int T[MAXN*3], M[MAXN*3], N, *X, *Y;
set<int, greater<int> > S;

void initTree(int idx, int l, int r){
    if(l==r){
        T[idx]=Y[l];
        return;
    }
    int m=(l+r)>>1, lidx=idx<<1, ridx=lidx+1;
    initTree(lidx, l, m);
    initTree(ridx, m+1, r);
    T[idx]=max(T[lidx], T[ridx]);
}

void updateTree(int idx, int l, int r, int t){
    if(l==r){
        T[idx]=Y[t];
        return;
    }
    int m=(l+r)>>1, lidx=idx<<1, ridx=lidx+1;
    if(t<=m) updateTree(lidx, l, m, t);
    if(t>m) updateTree(ridx, m+1, r, t);
    T[idx]=max(T[lidx], T[ridx]);
}

int queryTree(int idx, int l, int r, int s, int e){
    if(r<s || l>e) return 0;
    if(s<=l && r<=e) return T[idx];
    int m=(l+r)>>1, lidx=idx<<1, ridx=lidx+1;
    return max(queryTree(lidx, l, m, s, e), queryTree(ridx, m+1, r, s, e));
}

void initmultiply(int idx, int l, int r){
    if(l==r){
        M[idx]=X[l];
        return;
    }
    int lidx=idx<<1, ridx=lidx+1, m=(l+r)>>1;
    initmultiply(lidx, l, m);
    initmultiply(ridx, m+1, r);
    M[idx]=(long long)M[lidx]*M[ridx]%MOD;
}

void updatemultiply(int idx, int l, int r, int t){
    if(l==r){
        M[idx]=X[t];
        return;
    }
    int m=(l+r)>>1, lidx=idx<<1, ridx=lidx+1;
    if(t<=m) updatemultiply(lidx, l, m, t);
    if(t>m) updatemultiply(ridx, m+1, r, t);
    M[idx]=(long long)M[lidx]*M[ridx]%MOD;
}

int getmultiply(int idx, int l, int r, int s, int e){
    if(r<s|| l>e) return 1;
    if(s<=l && r<=e) return M[idx];
    int m=(l+r)>>1, lidx=idx<<1, ridx=lidx+1;
    return (long long)getmultiply(lidx, l, m, s, e)*getmultiply(ridx, m+1, r, s, e)%MOD;
}

int getans(){
    long long x=1, y, ans=0, ansy;
    set<int, greater<int> >::iterator pos, nxt, idx;
    for(pos=S.begin(); pos!=S.end(); ++pos){
        x=x*X[*pos];
        if(x>1e9) break;
    }
    if(pos==S.end()) --pos;
    if(pos!=S.begin()){
        nxt=pos; --nxt;
        x=1;
        if(x*(y=queryTree(1, 0, N-1, *pos, (*nxt)-1))>ans){
            ans=x*y;
            ansy=y;
            idx=pos;
        }
        pos=nxt, --nxt;
        for(; pos!=S.begin(); pos=nxt, --nxt){
            x=x*X[*pos];
            if(x*(y=queryTree(1, 0, N-1, *pos, (*nxt)-1))>ans){
                ans=x*y;
                ansy=y;
                idx=pos;
            }
        }
    }
    pos=S.begin();
    x=x*X[*pos];
    if(x*(y=queryTree(1, 0, N-1, *pos, N-1))>ans){
        ans=x*y;
        ansy=y;
        idx=pos;
    }
    return getmultiply(1, 0, N-1, 0, *idx)*ansy%MOD;
}

int init(int _N, int _X[], int _Y[]) {
    int i;
    N=_N, X=_X, Y=_Y;
    initTree(1, 0, N-1);
    initmultiply(1, 0, N-1);
    for(i=0; i<N; i++) if(X[i]>1) S.insert(i);
    S.insert(0);
    return getans();
}

int updateX(int pos, int val) {
    if(X[pos]>1 && val==1 && pos)
        S.erase(pos);
    else if(X[pos]==1 && val>1)
        S.insert(pos);
    X[pos]=val;
    updatemultiply(1, 0, N-1, pos);
    return getans();
}

int updateY(int pos, int val) {
    Y[pos]=val;
    updateTree(1, 0, N-1, pos);
    return getans();
}

Compilation message (stderr)

horses.cpp: In function 'void initmultiply(int, int, int)':
horses.cpp:47:11: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     M[idx]=(long long)M[lidx]*M[ridx]%MOD;
           ^
horses.cpp: In function 'void updatemultiply(int, int, int, int)':
horses.cpp:58:11: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     M[idx]=(long long)M[lidx]*M[ridx]%MOD;
           ^
horses.cpp: In function 'int getmultiply(int, int, int, int, int)':
horses.cpp:65:85: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return (long long)getmultiply(lidx, l, m, s, e)*getmultiply(ridx, m+1, r, s, e)%MOD;
                                                                                     ^
horses.cpp: In function 'int getans()':
horses.cpp:101:49: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return getmultiply(1, 0, N-1, 0, *idx)*ansy%MOD;
                                                 ^
horses.cpp:101:43: warning: 'ansy' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return getmultiply(1, 0, N-1, 0, *idx)*ansy%MOD;
                                           ^

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