oj.uz

답안 #876067

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
876067 2023-11-21T07:54:47 Z Elvin_Fritl 말 (IOI15_horses) C++17
0 / 100
 16 ms 19548 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 3e5 + 545 , inf = 1e9 + 199 , mod = 1e9 + 7;

    #include "horses.h"

 
struct segtree {
	ll tree[N*3];
	void update(int v,int l,int r,int pos,ll val) {
		if(l == r) {
			tree[v] = val; 
			return;
		}
		int mid = (l+r)>>1;
		if(pos <= mid) {
			update((v << 1 | 1), l, mid, pos, val);
		}
		else {
			update((v << 1 | 1), mid + 1, r, pos, val);
		}
		tree[v] = max(tree[(v << 1)], tree[(v << 1 | 1)]);
	}
	ll get(int v,int l,int r,int ml,int mr) {
		if(mr < l || r < ml || l > r){
			return 0LL;
		}
		if(ml <= l && r <= mr){
			return tree[v];
		}
		int mid = (l+r)>>1;
		return max(get((v << 1), l, mid, ml, mr), get((v << 1 | 1), mid + 1, r, ml, mr));
	}
	
};
int n;
ll x[N] , y[N];
set<int> s;
ll tmp = 1;
 
ll bp(ll x,ll m){
    if(m == 0){
        return 1LL;
    }
    if(m == 1){
        return x%mod;
    }
    if(m%2==0){
        return bp(x*x%mod,m/2)%mod;
    }
    return x*bp(x,m-1)%mod;
}

segtree S;


int calc() {
	ll res = 1 , ind = -1;
	assert((int)s.size() >= 2);
	auto it = --(--s.end());
	while(it != s.begin()) {
		res *= x[*it];
		ind = *it;
		if(res > inf){
			break;
		}
		--it;
	}
	it = s.lower_bound(ind);
	ll mx = 0; 
	res = 1;
	while((++it) != s.end()) {
		int i = *it;
		int j = *(++it);
		if(i != ind){
			res = res*x[i];
		}
		mx = max(mx, res * S.get(1, 0, n-1, i, j-1));
		++it;
	}
	mx %= mod;
	return (((tmp * bp(res, mod-2))%mod)*mx)%mod;
}


int init(int nn, int X[], int Y[]) {
	n = nn;
	for(int i=0;i<n;i++) {
		x[i] = X[i];
		y[i] = Y[i];
	}
	for(int i=0;i<N;i++) {
		S.update(1, 0, n - 1, i, y[i]);
	}
	s.insert(0);
	s.insert(n);
	for(int i=n-1;i>=0;i--) {
		if(x[i] > 1) {
			tmp = (tmp * x[i])%mod;
			s.insert(i); 
		}
	}
	return calc();
}
 
 
int updateX(int pos, int val) {
	tmp = (tmp * bp(x[pos], mod-2))%mod;
	x[pos] = val;
	tmp = (tmp*val)%mod;
	if(val > 1 || pos == 0){
		s.insert(pos);
	}
	else{
		s.erase(s.find(pos));
	}
	return calc();
}
 
int updateY(int pos, int val) {
	S.update(1, 0, n-1, pos, val);
	return calc();
}

Compilation message

horses.cpp: In function 'll bp(ll, ll)':
horses.cpp:44:10: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   44 | ll bp(ll x,ll m){
      |       ~~~^
horses.cpp:40:4: note: shadowed declaration is here
   40 | ll x[N] , y[N];
      |    ^
horses.cpp: In function 'int calc()':
horses.cpp:72:21: warning: conversion from 'll' {aka 'long long int'} to 'std::set<int>::key_type' {aka 'int'} may change value [-Wconversion]
   72 |  it = s.lower_bound(ind);
      |                     ^~~
horses.cpp:85:42: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   85 |  return (((tmp * bp(res, mod-2))%mod)*mx)%mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
0 / 17.0

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

Subtask #2
0 / 17.0

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

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 16 ms 19548 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
0 / 23.0

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