Submission #202434

#	Time	Username	Problem	Language	Result	Execution time	Memory
202434		anonymous	Horses (IOI15_horses)	C++14	100 / 100	198 ms	66680 KiB

horses

#include "horses.h"
#include<iostream>
#define MOD (1000000007LL)
#define LL long long
#define INF (1LL<<30)
#define MAXN 500005
using namespace std;
LL n, x[MAXN], y[MAXN];
class Segtree {
    LL ST[MAXN*4][5]; //mod product, actual (or inf), opt product, opt, prod of stuff to right of opt
public:
    void pushup(int cur) {
        ST[cur][0]=(ST[2*cur][0]*ST[2*cur+1][0])%MOD;
        ST[cur][1]=min(ST[2*cur][1]*ST[2*cur+1][1], INF);
        if (ST[2*cur][4] == INF || y[ST[2*cur][3]] <= ST[2*cur+1][2]*ST[2*cur][4]) {
            ST[cur][2] = min(ST[2*cur+1][2]*ST[2*cur][1], INF);
            ST[cur][3] = ST[2*cur+1][3];
            ST[cur][4] = ST[2*cur+1][4];
        } else {
            ST[cur][2] = ST[2*cur][2];
            ST[cur][3] = ST[2*cur][3];
            ST[cur][4] = min(ST[2*cur][4]*ST[2*cur+1][1], INF);
        }
    }
    void build(int l, int r, int cur) {
        if (l == r) {
            ST[cur][0] = x[l];
            ST[cur][1] = x[l];
            ST[cur][2] = min(x[l]*y[l], INF);
            ST[cur][3] = l;
            ST[cur][4] = 1;
        } else {
            int mid=(l+r)>>1;
            build(l, mid, 2*cur);
            build(mid+1, r, 2*cur+1);
            pushup(cur);
        }
    }
    void upd(int ind, int l, int r, int cur) {
        if (l > ind || r < ind) {return;}
        if (l == r) {
            ST[cur][0] = x[l];
            ST[cur][1] = x[l];
            ST[cur][2] = min(x[l]*y[l], INF);
            ST[cur][3] = l;
        } else {
            int mid=(l+r)>>1;
            upd(ind, l, mid, 2*cur);
            upd(ind, mid+1, r, 2*cur+1);
            pushup(cur);
        }
    }
    LL ask(int ind, int l, int r, int cur) { //ask for prefix mod product
        if (ind < l) {return(1);}
        if (r <= ind) {return(ST[cur][0]);}
        else {
            int mid=(l+r)>>1;
            return((ask(ind, l, mid, 2*cur)*ask(ind, mid+1, r, 2*cur+1))%MOD);
        }
    }
    LL opt() {return(ST[1][3]);}
} ST;

int init(int N, int X[], int Y[]) {
	n=N;
	for (int i=0; i<N; i++) {
        x[i] = X[i];
        y[i] = Y[i];
	}
	ST.build(0, N-1, 1);
	LL p = ST.opt(), prod = ST.ask(p, 0, N-1, 1);
	LL ans = (prod * y[p])%MOD;
	return( (int) ans);
}

int updateX(int pos, int val) {
	x[pos]=val;
	ST.upd(pos, 0, n-1, 1);
	LL p = ST.opt(), prod = ST.ask(p, 0, n-1, 1);
	LL ans = (prod * y[p])%MOD;
	return( (int) ans);
}

int updateY(int pos, int val) {
	y[pos]=val;
	ST.upd(pos, 0, n-1, 1);
	LL p = ST.opt(), prod = ST.ask(p, 0, n-1, 1);
	LL ans = (prod * y[p])%MOD;
	return( (int) ans);
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:71:45: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  LL p = ST.opt(), prod = ST.ask(p, 0, N-1, 1);
                                             ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:78:18: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  ST.upd(pos, 0, n-1, 1);
                 ~^~
horses.cpp:79:45: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  LL p = ST.opt(), prod = ST.ask(p, 0, n-1, 1);
                                             ^
horses.cpp:79:40: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  LL p = ST.opt(), prod = ST.ask(p, 0, n-1, 1);
                                       ~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:86:18: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  ST.upd(pos, 0, n-1, 1);
                 ~^~
horses.cpp:87:45: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  LL p = ST.opt(), prod = ST.ask(p, 0, n-1, 1);
                                             ^
horses.cpp:87:40: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  LL p = ST.opt(), prod = ST.ask(p, 0, n-1, 1);
                                       ~^~

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