oj.uz

답안 #1039452

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1039452 2024-07-30T22:34:44 Z HappyCapybara 말 (IOI15_horses) C++17
0 / 100
 340 ms 75860 KB 
#include "horses.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long

int n;
vector<pair<int,double>> stl;
vector<double> lazy;
vector<ll> stm;
vector<int> x, y;

void updatem(int pos, int val, int node=1, int tl=0, int tr=n-1){
	if (tl == tr){
		stm[node] = val;
		return;
	}
	int tm = (tl+tr)/2;
	if (pos <= tm) updatem(pos, val, node*2, tl, tm);
	else updatem(pos, val, node*2+1, tm+1, tr);
	stm[node] = (stm[node*2]*stm[node*2+1]) % 1000000007;
}

int querym(int l, int r, int node=1, int tl=0, int tr=n-1){
	//cout << l << " " << r << " " << tl << " " << tr << "\n";
	if (l <= tl && tr <= r) return stm[node];
	int tm = (tl+tr)/2;
	int res = 1;
	if (l <= tm) res = (res*querym(l, r, node*2, tl, tm)) % 1000000007;
	if (tm+1 <= r) res = (res*querym(l, r, node*2+1, tm+1, tr)) % 1000000007;
	return res;
}

void prop(int node, int tl, int tr){
	stl[node].second += lazy[node];
	if (tl != tr){
		lazy[node*2] += lazy[node];
		lazy[node*2+1] += lazy[node];
	}
	lazy[node] = 0;
}

pair<int,double> merge(int a, int b){
	if (stl[a].second > stl[b].second) return stl[a];
	return stl[b];
}

void updatel(int l, int r, double val, int node=1, int tl=0, int tr=n-1){
	if (l <= tl && tr <= r){
		lazy[node] += val;
		prop(node, tl, tr);
		return;
	}
	prop(node, tl, tr);
	int tm = (tl+tr)/2;
	if (l <= tm) updatel(l, r, val, node*2, tl, tm);
	if (tm+1 <= r) updatel(l, r, val, node*2+1, tm+1, tr);
	stl[node] = merge(node*2, node*2+1);
}

void updatelp(int pos, double val, int node=1, int tl=0, int tr=n-1){
	prop(node, tl, tr);
	if (tl == tr){
		stl[node].first = pos;
		stl[node].second += val;
		return;
	}
	int tm = (tl+tr)/2;
	if (pos <= tm) updatelp(pos, val, node*2, tl, tm);
	else updatelp(pos, val, node*2+1, tm+1, tr);
	stl[node] = merge(node*2, node*2+1);
}

int init(int N, int X[], int Y[]){
	n = N;
	stl.resize(4*N, {-1, 0});
	lazy.resize(4*N, 0);
	stm.resize(4*N, 1);
	x.resize(N);
	y.resize(N);
	for (int i=0; i<N; i++){
		y[i] = Y[i];
		x[i] = X[i];
		updatem(i, X[i]);
		updatelp(i, Y[i]);
		updatel(i, N-1, log(X[i]));
	}
	/*for (int i=1; i<4*N; i++){
		cout << stl[i].first << " " << stl[i].second << " | ";
		if ((i+1) == pow(2, floor(log2(i+1)))) cout << "\n";
	}*/
	return querym(0, stl[1].first)*y[stl[1].first] % 1000000007;
}

int updateX(int pos, int val){	
	updatel(pos, n-1, log(val)-log(x[pos]));
	x[pos] = val;
	return querym(0, stl[1].first)*y[stl[1].first] % 1000000007;
}

int updateY(int pos, int val){
	updatelp(pos, val-y[pos]);
	y[pos] = val;
	return querym(0, stl[1].first)*y[stl[1].first] % 1000000007;
}

Compilation message

horses.cpp: In function 'int querym(int, int, int, int, int)':
horses.cpp:26:41: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
   26 |  if (l <= tl && tr <= r) return stm[node];
      |                                         ^

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 340 ms 75860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -