oj.uz

Submission #62308

# Submission time Handle Problem Language Result Execution time Memory
62308 2018-07-28T04:27:05 Z nvmdava Horses (IOI15_horses) C++17
0 / 100
 81 ms 32204 KB 
#include "horses.h"
#include <bits/stdc++.h>

#define SIZE 500100
#define INF 1<<30
#define MOD 1000000007

using namespace std;

long long mult[SIZE * 3];
int maxLoc[SIZE * 3];
long double lazy[SIZE * 3], A[SIZE], maxValue[SIZE * 3];
int X[SIZE], Y[SIZE], N;

void update(int id, int l, int r, int k){
	if(l == k && r == k){
		mult[id] = X[l];
		return;
	}
	int m = (l + r) >> 1;
	if(m >=	k){
		update(id << 1, l, m, k);
	} else {
		update(id << 1 | 1,  m + 1, r, k);
	}
	
	mult[id] = mult[id << 1] * mult[id << 1 | 1] % MOD;
}

void add(int id,int l, int r,int L,int R, long double diff){
	if(l == L && r == R){
		maxValue[id] += diff;
		lazy[id] += diff;
		return;
	}
	if(lazy[id] != 0){
		lazy[id << 1] +=lazy[id];
		lazy[id << 1 | 1] +=lazy[id];
		maxValue[id << 1] +=lazy[id];
		maxValue[id << 1 | 1] +=lazy[id];
		lazy[id] = 0;
	}
	int m = (l + r) >> 1;
	if(R <= m){
		add(id << 1, l, m, L, R, diff);
	} else if(L > m){
		add(id << 1 | 1,m + 1, r, L, R, diff);
	} else {
		add(id << 1, l, m, L, R, diff);
		add(id << 1 | 1,m + 1, r, L, R, diff);
	}
	if(maxValue[id << 1] > maxValue[id << 1 | 1]){
		maxValue[id] = maxValue[id << 1];
		maxLoc[id] = maxLoc[id << 1];
	} else { 
		maxValue[id] = maxValue[id << 1 | 1];
		maxLoc[id] = maxLoc[id << 1 | 1];
	}
}

long long solve(int id, int l, int r,int L,int R){
	if(L >= l && r <= R){
		return mult[id];
	}
	int m = (l + r) >> 1;
	if(R <= m){
		return solve( id << 1, l, m, L , R);
	} else if(L > m){
		return solve( id << 1 | 1, m + 1, r, L, R);
	}
	return solve( id << 1, l, m, L , R) * solve( id << 1 | 1, m + 1, r, L, R) % MOD;
}

void build(int id, int l, int r){
	if(l == r){
		maxLoc[id] = l;
		mult[id] = X[l];
		maxValue[id] = A[l];
		return;
	}
	
	build(id << 1, l, (l + r) >> 1);
	build(id << 1 | 1, (l + r) >> 1 + 1, r);
	
	if(maxValue[id << 1] > maxValue[id << 1 | 1]){
		maxLoc[id] = maxLoc[id << 1];
		maxValue[id] = maxValue[id << 1];
	} else {
		maxLoc[id] = maxLoc[id << 1 | 1];
		maxValue[id] = maxValue[id << 1 | 1];
	}
	mult[id] = mult[id << 1] * mult[id << 1 | 1] % MOD;
}

int init(int n, int XX[], int YY[]) {
	N = n;
	for(int i = 1; i <= N ; i++){
		X[i] = XX[i - 1];
		Y[i] = YY[i - 1];
	}
	
	for(int i = 1; i <= N; i++){
		A[i] = A[i - 1] + log(X[i]);
	}
	
	for(int i = 1; i <= N; i++){
		A[i] += log(Y[i]);
	}
	
	build(1,1,N);
	return solve(1, 1, N , 1, maxLoc[1]) * Y[maxLoc[1]] % MOD;
}

int updateX(int pos, int val) {
	pos++;
    long double diff = log(val) - log(X[pos]);
    X[pos] = val;
    add(1, 1, N, pos, N, diff);
    update(1, 1, N, pos);
 
    return solve(1, 1, N, 1, maxLoc[1]) * Y[maxLoc[1]] % MOD;
}

int updateY(int pos, int val) {
	pos++;
	long double diff = log(val) - log(Y[pos]);
	Y[pos] = val;
	add(1,1,N,pos,pos,diff);
	
	return solve(1,1,N,1,maxLoc[1]) * Y[maxLoc[1]] % MOD;
}

Compilation message

horses.cpp: In function 'void build(int, int, int)':
horses.cpp:83:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  build(id << 1 | 1, (l + r) >> 1 + 1, r);
                                ~~^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:111:54: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return solve(1, 1, N , 1, maxLoc[1]) * Y[maxLoc[1]] % MOD;
                                                      ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:121:56: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return solve(1, 1, N, 1, maxLoc[1]) * Y[maxLoc[1]] % MOD;
                                                        ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:130:49: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return solve(1,1,N,1,maxLoc[1]) * Y[maxLoc[1]] % MOD;
                                                 ^

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Runtime error 5 ms 1000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1000 KB Output is correct
2 Runtime error 7 ms 1072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 81 ms 32204 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 32204 KB Output is correct
2 Runtime error 9 ms 32204 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 32204 KB Output is correct
2 Runtime error 6 ms 32204 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -