Submission #1035204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035204		Warinchai	Horses (IOI15_horses)	C++14	100 / 100	153 ms	119636 KiB

horses

#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
long long md=1e9+7;
long long inf=1e9+1;
long long y[500005];
long long x[500005];
int n;
struct node{
    long long y,rall,pre,suf,ans,all;
    node(long long _y=0,long long _rall=0,long long _pre=0,long long _suf=0,long long _ans=0,long long _all=0){
        y=_y,rall=_rall,pre=_pre,suf=_suf,ans=_ans,all=_all;
    }
    friend node operator+(node a,node b){
        node c;
        c.rall=(a.rall*b.rall)%md;
        c.all=min(a.all*b.all,inf);
        if(min(a.suf*b.pre,inf)>a.y){
            c.y=b.y;
            c.pre=min(a.all*b.pre,inf);
            c.suf=b.suf;
            c.ans=(a.rall*b.ans)%md;
        }else{
            c.y=a.y;
            c.pre=a.pre;
            c.suf=min(a.suf*b.all,inf);
            c.ans=a.ans;
        }
        return c;
    }
};
struct segtree{
    node info[2000005];
    void upd(int st,int en,int i,int pos,node val){
        if(st>pos||en<pos)return;
        if(st==en)return void(info[i]=val);
        int m=(st+en)/2;
        upd(st,m,i*2,pos,val);
        upd(m+1,en,i*2+1,pos,val);
        info[i]=info[i*2]+info[i*2+1];
    }
    void build(int st,int en,int i){
        //cerr<<st<<' '<<en<<"\n";
        if(st==en)return void(info[i]=node(y[st],x[st],min(x[st]*y[st],inf),1,(x[st]*y[st])%md,x[st]));
        int m=(st+en)/2;
        build(st,m,i*2);
        build(m+1,en,i*2+1);
        info[i]=info[i*2]+info[i*2+1];
    }
}tr;
int init(int N, int X[], int Y[]) {
    n=N;
    for(int i=1;i<=N;i++)x[i]=X[i-1],y[i]=Y[i-1];
    tr.build(1,N,1);
	return tr.info[1].ans;
}

int updateX(int pos, int val) {	
    pos++;
    x[pos]=val;
    tr.upd(1,n,1,pos,node(y[pos],x[pos],min(x[pos]*y[pos],inf),1,(x[pos]*y[pos])%md,x[pos]));
	return tr.info[1].ans;
}

int updateY(int pos, int val) {
	pos++;
    y[pos]=val;
    tr.upd(1,n,1,pos,node(y[pos],x[pos],min(x[pos]*y[pos],inf),1,(x[pos]*y[pos])%md,x[pos]));
	return tr.info[1].ans;
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:55:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   55 |  return tr.info[1].ans;
      |         ~~~~~~~~~~~^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:62:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   62 |  return tr.info[1].ans;
      |         ~~~~~~~~~~~^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:69:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   69 |  return tr.info[1].ans;
      |         ~~~~~~~~~~~^~~

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