Submission #399521

#	Time	Username	Problem	Language	Result	Execution time	Memory
399521		bigg	Horses (IOI15_horses)	C++14	100 / 100	590 ms	106052 KiB

horses

#include "horses.h"
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 5e5 + 10;
const ll MOD = 1e9 + 7;
#define esq(x) x << 1 
#define dir(x) (x<<1) | 1
#define mid(x,y,t) ((x+y)>>1) + t

ll Y[MAXN], X[MAXN];
int n;

struct nodeseg
{
	ll v, id, xm;
	bool flag;
	nodeseg(ll _v = 0, ll _id = 0, ll _xm = 0, bool f = 0){
		v = _v;
		id = _id;
		xm = _xm;
		flag = f;
	}
	nodeseg operator + (nodeseg b){
		if(flag && b.flag) return nodeseg(0,0,0,1);
		if(flag) return b;
		if(b.flag) return *this;
		nodeseg ans;
		if(v >= b.v){
			ans.id = id;
			ans.v = v;
		}else{
			ans.id = b.id;
			ans.v = b.v;
		}
		ans.xm = (xm * b.xm)%MOD;
		return ans;
	}
}seg[4*MAXN];

void build(int node, int x, int y){
	if(x == y){
		seg[node] = nodeseg(Y[x], x, X[x], 0);
		return;
	}
	build(esq(node), x, mid(x,y,0));
	build(dir(node), mid(x,y,1), y);
	seg[node] = seg[esq(node)] + seg[dir(node)];
}

void update(int node, int x, int y, int id, int t){
	if(x > id || y < id ) return;
	if(x == y){
		seg[node].v = Y[x];
		seg[node].xm = X[x];
		return;
	}
	if(id <= mid(x,y,0)) update(esq(node), x, mid(x,y,0), id, t);
	else update(dir(node), mid(x,y,1), y, id, t);
	seg[node] = seg[esq(node)] + seg[dir(node)];
}
nodeseg query(int node, int x, int y, int l, int r){
	if(x > r || y < l || y < x || r  < l) return nodeseg(0,-1,1,0);
	if(x >= l && y <= r) return seg[node];
	if(r <= mid(x,y,0)) return query(esq(node), x, mid(x,y,0), l, r);
	else if(l > mid(x,y,0)) return query(dir(node), mid(x,y,1), y, l, r);
	nodeseg e = query(esq(node), x, mid(x,y,0), l, r);
	nodeseg d = query(dir(node), mid(x,y,1), y, l, r);
	return e + d;
}

set<int> ids;

ll makeans(){
	if(ids.empty()) return (query(1,1,n,1,n).v)%MOD;
	set<int> :: iterator it = ids.end();
	it--;
	ll ans = 0, id = 0;
	int r = n;
	while(true){
		//printf("%d %d\n", r, *it);
		
		
		nodeseg q = query(1,1,n,*it,r);
		
		if(q.v >= ans) ans = q.v, id = q.id;
		
		ans *= X[*it];
		r = *it -1;
		//printf("%d %d\n", r, *it);
		if(it == ids.begin()) break;
		if(ans  > (ll) 1e9) break;
		
		it--;
		
	}
	//printf("%d\n", r);
	
	nodeseg q = query(1,1,n,1,r);
	if(q.v >= ans) ans = q.v, id = q.id;
	
	return (query(1,1,n,1,id).xm*Y[id])%MOD;
}

int init(int N, int x[], int y[]) {
	n = N;
	for(int i = 0; i < N; i++){
		X[i+1] = x[i];
		Y[i+1] = y[i];
		
	}
	build(1,1,n);
	for(int i = 1; i <= n; i++) if(X[i] >= 2) ids.insert(i);

	return makeans();
}

int updateX(int pos, int val) {

	pos++;
	if(X[pos] >= 2)ids.erase(pos);
	X[pos] = val;
	if(X[pos] >= 2) ids.insert(pos);
	update(1,1,n,pos,1);
	return makeans();
}

int updateY(int pos, int val) {
	pos++;
	Y[pos] = val;
	update(1,1,n,pos,0);
	return makeans();
	
}

Compilation message (stderr)

horses.cpp: In function 'll makeans()':
horses.cpp:103:24: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  103 |  return (query(1,1,n,1,id).xm*Y[id])%MOD;
      |                        ^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:116:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  116 |  return makeans();
      |         ~~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:126:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  126 |  return makeans();
      |         ~~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:133:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  133 |  return makeans();
      |         ~~~~~~~^~

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