oj.uz

답안 #823416

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
823416 2023-08-12T13:37:17 Z _martynas 말 (IOI15_horses) C++11
0 / 100
 348 ms 40492 KB 
#include "horses.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#warning change mxn
const int mxn = 5e5+5;
const int mxval = 1e9;
const int mod = 1e9+7;

struct Seg {
	int mx[4*mxn];
	int get(int u, int l, int r, int ql, int qr) {
		if(qr < l || r < ql) return 0;
		if(ql <= l && r <= qr) return mx[u];
		int m = (l+r)/2;
		return max(get(2*u, l, m, ql, qr), get(2*u+1, m+1, r, ql, qr));
	}
	void set(int u, int l, int r, int i, int x) {
		if(l == r) {
			mx[u] = x; return;
		}
		int m = (l+r)/2;
		if(i <= m) set(2*u, l, m, i, x);
		else set(2*u+1, m+1, r, i, x);
		mx[u] = max(mx[2*u], mx[2*u+1]);
	}
} seg;
int n;
int x[mxn], y[mxn];
set<int> st;
ll tot = 1;

ll mod_pow(ll a, ll b) {
	ll ans = 1;
	while(b) {
		if(b & 1) ans = ans*a%mod;
		a = a*a%mod;
		b >>= 1;
	}
	return ans;
}

int init(int N, int X[], int Y[]) {
	n = N;
	copy(X, X+n, x); copy(Y, Y+n, y);
	for(int i = 0; i < N; i++) seg.set(1, 0, n-1, i, Y[i]);
	st.insert(n-1);
	tot = X[n-1];
	for(int i = n-2; i >= 0; i--) {
		if(X[i] > 1) {
			tot = tot*X[i]%mod;
			st.insert(i);
		}
	}
	return 0;
}

int get() {
	ll acc = 1;
	int last = -1;
	auto rit = st.rbegin();
	while(rit != st.rend()) {
		acc *= x[*rit];
		last = *rit;
		if(acc > mxval) break;
		rit = next(rit);
	}
	auto it = st.lower_bound(last);
	int prev = acc > mxval ? last : 0;
	ll mx = 0; acc = 1;
	while(it != st.end()) {
		int i = *it;
		ll best_y = seg.get(1, 0, n-1, prev, i);
		if(i != last) acc = acc*x[i];
		mx = max(mx, acc*best_y);
		prev = i+1;
		it = next(it);
	}
	//printf("mx = %lld\n", mx);
	mx %= mod;
	return tot*mod_pow(acc, mod-2)%mod*mx%mod;
}

int updateX(int pos, int val) {
	tot = tot*mod_pow(x[pos], mod-2)%mod;
	x[pos] = val;
	tot = tot*val%mod;
	if(val > 1 || pos == n-1) st.insert(pos);
	else (st.erase(pos));
	return get();
}

int updateY(int pos, int val) {
	seg.set(1, 0, n-1, pos, val);
	return get();
}

// int main(int argc, char const *argv[])
// {
// 	int N;
// 	cin >> N;
// 	int X[N], Y[N];
// 	for(int i = 0; i < N; i++) cin >> X[i];
// 	for(int i = 0; i < N; i++) cin >> Y[i];
// 	init(N, X, Y);
// 	int M;
// 	cin >> M;
// 	for(int i = 0; i < M; i++) {
// 		int type; cin >> type;
// 		int pos, val; cin >> pos >> val;
// 		if(type == 1) {
// 			cout << "resp: " << updateX(pos, val) << "\n";
// 		}
// 		else {
// 			cout << "resp: " << updateY(pos, val) << "\n";
// 		}
// 	}
// 	return 0;
// }

Compilation message

horses.cpp:8:2: warning: #warning change mxn [-Wcpp]
    8 | #warning change mxn
      |  ^~~~~~~
horses.cpp: In function 'int get()':
horses.cpp:84:39: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   84 |  return tot*mod_pow(acc, mod-2)%mod*mx%mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
0 / 17.0

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

Subtask #2
0 / 17.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 23.0

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