제출 #1289695

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289695		Minbaev	말 (IOI15_horses)	C++20	100 / 100	765 ms	31928 KiB

horses

//#include "grader.cpp"
#include "horses.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;
using namespace __gnu_pbds;

#define pb      push_back
#define all(x)  x.begin(),x.end()
#define ar      array
#define mrand(a, b)   uniform_int_distribution<int>(a, b)(rng)

template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}

template<class T> using ste = tree<T, null_type, less_equal<T>,
rb_tree_tag, tree_order_statistics_node_update>;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const long long inf = 1e17 + 7;
const int mod = 1e9 + 7;
const int N = 5e5 + 5;
const int md = 998244353;

int binpow(int a, int b, int m){
    if(b == 0)return 1;
    if(b % 2 == 0){
        int c = binpow(a,b/2,m);
        return (c*c)%m;
    }
    return (binpow(a,b-1,m)*a)%m;
}

int divi(int a, int b, int m){
    return (a*(binpow(b,m-2, m)))%m;
}

vector<int>a(N), b(N);
int n;
long long t[N*4];
int mxi[N*4], cnt[N*4];

void update(int tl, int tr, int v, int pos, int val){
	if(tl == tr){
		t[v] = val;
		return;
	}
	int tm = (tl + tr) / 2;
	
	if(pos <= tm)
		update(tl, tm, v*2, pos, val);
	else 
		update(tm+1, tr, v*2+1, pos, val);
	t[v] = (t[v*2] * t[v*2+1]) % mod;
}

long long get(int tl, int tr, int v, int l, int r){
	if(r < tl || tr < l || r < l)return 1ll;
	if(l <= tl && tr <= r){
		return t[v];
	}
	int tm = (tl + tr) / 2;
	
	return (get(tl, tm, v*2, l, r) * get(tm+1, tr, v*2+1, l, r)) % mod;
}
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
void update2(int tl, int tr, int v, int pos, int val){
	if(tl == tr){
		mxi[v] = val;
		return;
	}
	int tm = (tl + tr) / 2;
	
	if(pos <= tm)
		update2(tl, tm, v*2, pos, val);
	else 
		update2(tm+1, tr, v*2+1, pos, val);
	mxi[v] = max(mxi[v*2], mxi[v*2+1]);
}

int get2(int tl, int tr, int v, int l, int r){
	if(r < tl || tr < l || r < l)return 0;
	if(l <= tl && tr <= r){
		return mxi[v];
	}
	int tm = (tl + tr) / 2;
	
	return max(get2(tl, tm, v*2, l, r), get2(tm+1, tr, v*2+1, l, r));
}

//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
void upd_cnt(int tl, int tr, int v, int pos, int val){
	if(tl == tr){
		cnt[v] = val;
		return;
	}
	int tm = (tl + tr) / 2;
	
	if(pos <= tm)
		upd_cnt(tl, tm, v*2, pos, val);
	else 
		upd_cnt(tm+1, tr, v*2+1, pos, val);
	cnt[v] = cnt[v*2] + cnt[v*2+1];
}

int get_cnt(int tl, int tr, int v, int l, int r){
	if(r < tl || tr < l || r < l)return 0;
	if(l <= tl && tr <= r){
		return cnt[v];
	}
	int tm = (tl + tr) / 2;
	
	return (get_cnt(tl, tm, v*2, l, r) + get_cnt(tm+1, tr, v*2+1, l, r));
}


//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------

vector<int>rb(N), vla(N), lb(N, -1);

long long fi(int ind, int val){
	long long sum = get(0, n, 1, 0, ind);
	long long u = (sum * val) % mod;
	return u;
}

int init(int N, int X[], int Y[]){
	n = N;
	for(int i = 0;i<n;i++){
		b[i] = Y[i];
		a[i] = X[i];
		update(0, n, 1, i, a[i]);
		update2(0, n, 1, i, b[i]);
		if(a[i] > 1)
			upd_cnt(0, n, 1, i, 1);
		else
			upd_cnt(0, n, 1, i, 0);
	}
	
	for(int i = 0;i<n;i++){
		if(i == 0){
			lb[i] = i;
			rb[i] = i;
			continue;
		}
		if(a[i] == 1){
			lb[i] = lb[i-1];
			rb[i] = i;
			rb[lb[i]] = i;
		}
		if(a[i] > 1){
			lb[i] = i;
			rb[i] = i;
		}
	}
	
	for(int i = 0;i<n;i++){
		vla[i] = get2(0, n, 1, i, rb[i]);
	}
	
	
	int l = 0, r = n-1, ans = 0;
	while(l <= r){
		int mid = (l + r) / 2;
		
		if(get_cnt(0, n, 1, mid, n) >= 32){
			ans = mid;
			l = mid + 1;
		}
		else r = mid - 1;
	}
	
	long long mx = -1, sum = 1, val = -1;
	
	for(int i = ans;i<n;){
		int iop = rb[i];
		
		int x = X[i];
		int y = vla[i];
		
		if(mx == -1){
			mx = i;
			sum = 1;
			val = y;
		}
		else{
			sum *= x;
			
			if(val / y < sum){
				mx = i;
				sum = 1;
				val = y;
			}
		}
		
		i = iop + 1;
	}
	
	/*cout << "\n";
	for(int i = 0;i<n;i++)cout << vla[i] << " ";
	cout << "\n";
	for(int i = 0;i<n;i++)cout << rb[i] << " ";
	cout << "\n\n";
	*/
	return fi(mx, val);
	
	
}

int updateX(int pos, int vl){
	update(0, n, 1, pos, vl);
	
	if(a[pos] != vl){
		if(vl == 1){
			int l2 = 0, r2 = pos-1, ans2 = 0;
			while(l2 <= r2){
				int mid = (l2 + r2) / 2;
				
				if(get_cnt(0, n, 1, mid, pos-1) == 0){
					r2 = mid - 1;
				}
				else {
					ans2 = mid;
					l2 = mid + 1;
				}
			}
			int yu = rb[pos];
			rb[pos] = pos;
			rb[ans2] = yu;
			vla[pos] = b[pos];
			vla[ans2] = get2(0, n, 1, ans2, rb[ans2]);
		}
		else if(a[pos] == 1){
			int l2 = 0, r2 = pos-1, ans2 = 0;
			while(l2 <= r2){
				int mid = (l2 + r2) / 2;
				
				if(get_cnt(0, n, 1, mid, pos - 1) == 0){
					r2 = mid - 1;
				}
				else {
					ans2 = mid;
					l2 = mid + 1;
				}
			}
			rb[pos] = rb[ans2];
			if(ans2 != pos)rb[ans2] = pos - 1;
			vla[pos] = get2(0, n, 1, pos, rb[pos]);
			vla[ans2] = get2(0, n, 1, ans2, rb[ans2]); 
		}
	}
	
	a[pos] = vl;
//	cout << "\n";
//	for(int i = 0;i<n;i++)cout << vla[i] << " ";
//	cout << "\n";
//	for(int i = 0;i<n;i++)cout << rb[i] << " ";
//	cout << "\n\n";
	
	if(vl == 1)
		upd_cnt(0, n, 1, pos, 0);
	else
		upd_cnt(0, n, 1, pos, 1);
		
		
	int l = 0, r = n-1, ans = 0;
	while(l <= r){
		int mid = (l + r) / 2;
		
		if(get_cnt(0, n, 1, mid, n) >= 32){
			ans = mid;
			l = mid + 1;
		}
		else r = mid - 1;
	}
	
	long long mx = -1, sum = 1, val = -1;
	
	for(int i = ans;i<n;){
		int iop = rb[i];
		
		int x = a[i];
		int y = vla[i];
		
		if(mx == -1){
			mx = i;
			sum = 1;
			val = y;
		}
		else{
			sum *= x;
			
			if(val / y < sum){
				mx = i;
				sum = 1;
				val = y;
			}
		}
		
		i = iop + 1;
	}
	
	return fi(mx, val);
	
}

int updateY(int pos, int vl){
	b[pos] = vl;
	update2(0, n, 1, pos, vl);
	
	int l2 = 0, r2 = pos, ans2 = 0;
	while(l2 <= r2){
		int mid = (l2 + r2) / 2;
		
		if(get_cnt(0, n, 1, mid, pos) == 0){
			r2 = mid - 1;
		}
		else {
			ans2 = mid;
			l2 = mid + 1;
		}
	}
//	cout << ans2 << "\n";
	
	vla[ans2] = get2(0, n, 1, ans2, rb[ans2]);
	if(ans2 != pos)vla[pos] = vl;
//	for(int i = 0;i<n;i++){
//		cout << vla[i] << ' ';
//	}
//	cout << "\n";
	
	int l = 0, r = n-1, ans = 0;
	while(l <= r){
		int mid = (l + r) / 2;
		
		if(get_cnt(0, n, 1, mid, n) >= 32){
			ans = mid;
			l = mid + 1;
		}
		else r = mid - 1;
	}
	
	long long mx = -1, sum = 1, val = -1;
	
	for(int i = ans;i<n;){
		int iop = rb[i];
		
		int x = a[i];
		int y = vla[i];
		
		if(mx == -1){
			mx = i;
			sum = 1;
			val = y;
		}
		else{
			sum *= x;
			
			if(val / y < sum){
				mx = i;
				sum = 1;
				val = y;
			}
		}
		
		i = iop + 1;
	}
	
	return fi(mx, val);
}

/*
7
0 2 1
6 2 1
7 2 1
12 2 1
14 2 1
18 2 1
21 2 1
10
1
2
3
4
5
6
7
8
9
10
*/
 /*signed main()
{
//  freopen("seq.in", "r", stdin);
//  freopen("seq.out", "w", stdout);
    ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
    int tt=1;// cin >> tt;
    while(tt--)solve();

}*/

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 23 / 23
• Subtask 5: 23 / 23