Submission #62306

#	Time	Username	Problem	Language	Result	Execution time	Memory
62306		tugushka	Horses (IOI15_horses)	C++14	100 / 100	552 ms	280552 KiB

horses

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

#define mod 1000000007
#define L(x) ((x)<<1)
#define R(x) (((x)<<1)|1)

struct Node{
	double sumx, y, max_val;
	int res, modx, xx, yy;
	
	void print(){
		cerr << "DBG : \n";
		cerr << sumx << ' ' << max_val << endl;
		cerr << res << endl;
	}
} tree[1<<21];

int n;

void update(int l, int r, int x, int pos, int dx, int dy){
	if( r < pos || pos < l) return;
	if( l == pos && l == r ){
		if( dx ) tree[x].sumx = log(dx), tree[x].xx = dx;
		if( dy ) tree[x].y = log(dy), tree[x].yy = dy;
		tree[x].max_val = tree[x].sumx + tree[x].y;
		tree[x].res = 1LL * tree[x].xx * tree[x].yy % mod;
		tree[x].modx = 1LL * tree[x].xx % mod;
		return;
	}
	
	int mid = (l+r)>>1;
	update( l, mid, L(x), pos, dx, dy );
	update( mid+1, r, R(x), pos, dx, dy );
	
	tree[x].sumx = tree[L(x)].sumx + tree[R(x)].sumx;
	tree[x].modx = 1LL * tree[L(x)].modx * tree[R(x)].modx % mod;
	if( tree[L(x)].max_val < tree[R(x)].max_val + tree[L(x)].sumx ){
		tree[x].max_val = tree[R(x)].max_val + tree[L(x)].sumx;
		tree[x].res = 1LL * tree[R(x)].res * tree[L(x)].modx % mod;
	}
	else{
		tree[x].max_val = tree[L(x)].max_val;
		tree[x].res = tree[L(x)].res;
	}
	
//	cerr << l << ' ' << r << ' ' << x << endl;
//	tree[x].print();
	
	return;
}

int init(int N, int X[], int Y[]) {
	n = N;
//	cerr << n << endl;
	for(int i = 0 ; i < n ; i++){
		update( 0, n-1, 1, i, X[i], Y[i] );
	}
//	cerr << "Done\n";
	return tree[1].res;
}

int updateX(int pos, int val) {	
	update(0, n-1, 1, pos, val, 0);
	return tree[1].res;
}

int updateY(int pos, int val) {
	update(0, n-1, 1, pos, 0, val);
	return tree[1].res;
}

Compilation message (stderr)

horses.cpp: In function 'void update(int, int, int, int, int, int)':
horses.cpp:28:47: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   tree[x].res = 1LL * tree[x].xx * tree[x].yy % mod;
                                               ^
horses.cpp:29:35: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   tree[x].modx = 1LL * tree[x].xx % mod;
                                   ^
horses.cpp:38:57: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  tree[x].modx = 1LL * tree[L(x)].modx * tree[R(x)].modx % mod;
                                                         ^
horses.cpp:41:56: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   tree[x].res = 1LL * tree[R(x)].res * tree[L(x)].modx % mod;
                                                        ^

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