Submission #831835

#	Time	Username	Problem	Language	Result	Execution time	Memory
831835		ttamx	Horses (IOI15_horses)	C++14	100 / 100	151 ms	70852 KiB

horses

#include "horses.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=5e5+5;
const int K=1<<20;
const ll mod=1e9+7;

int n;
int X[N],Y[N];

struct segtree{
	struct node{
		ll x,y,pre,suf,all,ans;
		node(){}
		node(ll x,ll y):x(x),y(y),pre(x),suf(1),all(x),ans(x*y%mod){}
		friend node operator+(node l,node r){
			node res;
			res.x=l.x*r.x%mod;
			res.all=min(l.all*r.all,mod);
			if(l.y>min(l.suf*r.pre,mod)*r.y){
				res.y=l.y;
				res.pre=l.pre;
				res.suf=min(l.suf*r.all,mod);
				res.ans=l.ans;
			}else{
				res.y=r.y;
				res.pre=min(l.all*r.pre,mod);
				res.suf=r.suf;
				res.ans=l.x*r.ans%mod;
			}
			return res;
		}
	}t[K];
	void build(int l,int r,int i){
		if(l==r)return void(t[i]=node(X[l],Y[l]));
		int m=(l+r)/2;
		build(l,m,i*2);
		build(m+1,r,i*2+1);
		t[i]=t[i*2]+t[i*2+1];
	}
	void build(){
		build(1,n,1);
	}
	void update(int l,int r,int i,int x){
		if(x<l||r<x)return;
		if(l==r)return void(t[i]=node(X[l],Y[l]));
		int m=(l+r)/2;
		update(l,m,i*2,x);
		update(m+1,r,i*2+1,x);
		t[i]=t[i*2]+t[i*2+1];
	}
	void update(int x){
		update(1,n,1,x);
	}
}s;

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];
	s.build();
	return s.t[1].ans;
}

int updateX(int pos, int val) {
	pos++;
	X[pos]=val;
	s.update(pos);
	return s.t[1].ans;
}

int updateY(int pos, int val) {
	pos++;
	Y[pos]=val;
	s.update(pos);
	return s.t[1].ans;
}

Compilation message (stderr)

horses.cpp: In constructor 'segtree::node::node(ll, ll)':
horses.cpp:19:16: warning: declaration of 'y' shadows a member of 'segtree::node' [-Wshadow]
   19 |   node(ll x,ll y):x(x),y(y),pre(x),suf(1),all(x),ans(x*y%mod){}
      |             ~~~^
horses.cpp:17:8: note: shadowed declaration is here
   17 |   ll x,y,pre,suf,all,ans;
      |        ^
horses.cpp:19:11: warning: declaration of 'x' shadows a member of 'segtree::node' [-Wshadow]
   19 |   node(ll x,ll y):x(x),y(y),pre(x),suf(1),all(x),ans(x*y%mod){}
      |        ~~~^
horses.cpp:17:6: note: shadowed declaration is here
   17 |   ll x,y,pre,suf,all,ans;
      |      ^
horses.cpp: In constructor 'segtree::node::node(ll, ll)':
horses.cpp:19:16: warning: declaration of 'y' shadows a member of 'segtree::node' [-Wshadow]
   19 |   node(ll x,ll y):x(x),y(y),pre(x),suf(1),all(x),ans(x*y%mod){}
      |             ~~~^
horses.cpp:17:8: note: shadowed declaration is here
   17 |   ll x,y,pre,suf,all,ans;
      |        ^
horses.cpp:19:11: warning: declaration of 'x' shadows a member of 'segtree::node' [-Wshadow]
   19 |   node(ll x,ll y):x(x),y(y),pre(x),suf(1),all(x),ans(x*y%mod){}
      |        ~~~^
horses.cpp:17:6: note: shadowed declaration is here
   17 |   ll x,y,pre,suf,all,ans;
      |      ^
horses.cpp: In constructor 'segtree::node::node(ll, ll)':
horses.cpp:19:16: warning: declaration of 'y' shadows a member of 'segtree::node' [-Wshadow]
   19 |   node(ll x,ll y):x(x),y(y),pre(x),suf(1),all(x),ans(x*y%mod){}
      |             ~~~^
horses.cpp:17:8: note: shadowed declaration is here
   17 |   ll x,y,pre,suf,all,ans;
      |        ^
horses.cpp:19:11: warning: declaration of 'x' shadows a member of 'segtree::node' [-Wshadow]
   19 |   node(ll x,ll y):x(x),y(y),pre(x),suf(1),all(x),ans(x*y%mod){}
      |        ~~~^
horses.cpp:17:6: note: shadowed declaration is here
   17 |   ll x,y,pre,suf,all,ans;
      |      ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:65:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   65 |  return s.t[1].ans;
      |         ~~~~~~~^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:72:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   72 |  return s.t[1].ans;
      |         ~~~~~~~^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:79:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   79 |  return s.t[1].ans;
      |         ~~~~~~~^~~

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