| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 955482 | PoPularPlusPlus | 말 (IOI15_horses) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) x.begin(),x.end()
#define vf first
#define vs second
const int mod = 1000000007;
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
const int N = 500003 , L = 70;
struct Seg {
int siz;
vector<ll> sum;
ll Nutral = 1;
void init(int n){
siz = 1;
while(siz < n)siz *= 2;
siz *= 2;
sum.resize(siz * 2 , Nutral);
}
void build(vector<int>& a , int x, int lx , int rx){
if(rx - lx == 1){
if(lx < (int)a.size())sum[x] = a[lx];
return;
}
int m = (lx + rx)/2;
build(a , 2 * x + 1 , lx , m);
build(a , 2 * x + 2 , m , rx);
sum[x] = (sum[2 * x + 1] * sum[2 * x + 2])%mod;
}
void build(vector<int>& a){
return build(a , 0 , 0 , siz);
}
void set(int i , int v ,int x , int lx , int rx){
if(rx - lx == 1){
sum[x] = v;
return;
}
int m = (lx + rx)/2;
if(i < m){
set(i , v , 2 * x + 1 , lx , m);
}
else set(i , v , 2 * x + 2 , m , rx);
sum[x] = (sum[2 * x + 1] * sum[2 * x + 2])%mod;
}
void set(int i , int v){
set(i , v , 0 , 0 , siz);
}
int sums(int l , int r , int x , int lx , int rx){
if(l >= rx || r <= lx)return Nutral;
if(lx >= l && rx <= r)return sum[x];
int m = (lx + rx)/2;
return (sums(l , r , 2 * x + 1 , lx , m) * sums(l , r , 2 * x +2 , m , rx))%mod;
}
int sums(int l , int r){
return sums(l , r , 0 , 0 , siz);
}
};
struct SegMX {
vector<ll> v;
int siz;
void init(int n){
siz = 1;
while(siz < n)siz *= 2;
v.assign(siz * 2 , 0);
}
void build(vector<int>& a , int x , int lx , int rx){
if(rx - lx == 1){
if(lx < a.size()){
v[x] = a[lx];
}
return;
}
int m = (lx + rx)/2;
build(a , 2*x+1,lx,m);
build(a , 2 * x + 2 , m , rx);
v[x] = max(v[2 * x + 1] , v[2*x+2]);
}
void build(vector<int>& a){
buld(a , 0 , 0 , siz);
}
void set(int i , int val , int x , int lx, int rx){
if(rx - lx == 1){
v[x] = val;
return;
}
int m = (lx + rx)/2;
if(i < m){
set(i , val ,2 * x + 1 , lx ,m);
}
else {
set(i , val , 2 * x + 2, m , rx);
}
v[x] = max(v[2*x+1] , v[2*x+2]);
}
void set(int i , int val){
set(i , val , 0 , 0, siz);
}
ll find(int l , int r , int x , int lx, int rx){
if(lx >= r || l >= rx)return 0;
if(lx >= l && rx <= r)return v[x];
int m = (lx + rx)/2;
return max(find(l,r,2*x+1,lx,m),find(l , r , 2 * x + 2 , m ,rx));
}
ll find(int l , int r){
return find(l , r , 0 , 0 , siz);
}
};
int n;
vector<int> x,y;
set<int> s,s1;
SegMX st;
Seg st_sum;
vector<pair<int,ll>> last;
int cal(){
int pos = -1;
ll multi = 1;
if(v.size() < L){
int right = n;
auto it = s.upper_bound(0);
if(it != s.end()){
right = *it;
}
cur = st.find(0,right);
if(v.size()){
int idx = v[0].vf;
if(x[idx] * v[0].vs >= cur){
pos = 0;
}
else {
multi *= x[idx];
}
}
}
for(int i = 1; i < v.size(); i++){
int idx = v[i].vf;
if(multi >= 1e9){
pos = i;
multi = 1;
}
else {
if(x[idx] * v[i].vs >= v[i-1].vs){
pos = i;
}
else {
multi *= x[idx];
}
}
}
return (st_sum(x[v[pos].vf] + 1) * v[pos].vs) % mod;
}
int init(int n1 , vector<int> x1 , vector<int> y1){
n = n1;
x = x1;
y = y1;
s.insert(0);
for(int i = 0; i < n; i++){
if(x[i] > 1){
s.insert(i);
}
}
st.init(n + 1);
st.build(y);
st_sum.init(n + 1);
st_sum.build(y);
for(int i = n - 1; i >= 0 && v.size() < L; i--){
if(x[i] > 1){
auto it = s.upper_bound(i);
int right = i;
if(it == s.end()){
right = n;
}
else right = (*it);
v.pb(mp(i,st.find(i,right)));
}
}
reverse(all(v));
return cal();
}
int updateX(int pos , int val){
pos--;
int toerase = -1;
for(int i = 0; i < v.size() && val == 1; i++){
if(x[v[i].vf] == pos){
toerase = i;
break;
}
}
if(toerase != -1){
v.erase(v.begin()+toerase);
s.erase(toerase);
if(v.size()){
auto it = s.lower_bound(toerase);
if(it != s.begin()){
auto it1 = it;
it--;
vector<pair<int,ll>> v1;
v1.pb(mp(*it,st.find(*it,*it1)));
for(auto tp : v){
v1.pb(tp);
}
v = v1;
}
}
}
else {
if(val == 1 && s.find(pos)!=s.end()){
return cal();
}
if(val > 1)s.insert(pos);
if(v.size() == 0 || pos > x[v[0].vf]){
v.erase(v.begin());
auto it = s.upper_bound(pos);
int right = n;
if(it!=s.end()){
right = *it;
}
v.pb(mp(pos , st.find(pos , right)));
}
}
st_sum.set(pos , val);
return cal();
}
int updateY(int pos , int val){
pos--;
st.set(pos , val);
if(v.size() && ix[v[0].vf] <= pos){
int cur = 0;
for(int i = 0; i < v.size() && x[v[i].vf] <= pos; i++){
cur = i;
}
int right = n;
if(cur + 1 < v.size()){
right = x[v[cur+1].vf];
v[cur].vs = st.find(x[v[i].vf] , right);
}
}
return cal();
}
void solve(){
int n;
cin >> n;
vector<int> a, b;
for(int i = 0; i < n; i++){
int x;
cin >> x;
a.pb(x);
}
for(int i = 0; i < n; i++){
int x;
cin >> x;
b.pb(x);
}
int m;
cin >> m;
cout << init(n , a , b) << '\n';
while(m--){
int t;
cin >> t;
int pos , val;
cin >> pos >> val;
if(t == 1){
cout<< updateX(pos , val) << '\n';
}
else cout << updateY(pos , val) << '\n';
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//int t;cin>>t;
//while(t--)
solve();
return 0;
}