| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1134000 | ackhava | 말 (IOI15_horses) | C++20 | 0 ms | 0 KiB |
#include "horses.h"
#include <bits/stdc++.h>
#define REP(v, i, j) for (int v = i; v != j; v++)
#define FORI(v) for (auto i : v)
#define FORJ(v) for (auto j : v)
#define OUT(v, a) \
FORI(v) \
cout << i << a;
#define OUTS(v, a, b) \
cout << v.size() << a; \
OUT(v, b)
#define in(a, n) \
REP(i, 0, n) \
cin >> a[i];
#define SORT(v) sort(begin(v), end(v))
#define REV(v) reverse(begin(v), end(v))
#define MEMSET(m) memset(m, -1, sizeof m)
#define pb push_back
#define fi first
#define se second
#define detachIO \
ios_base::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
using namespace std;
template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
bool operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) {
if(__x.size() != __y.size()) return false;
return std::equal(__x.begin(), __x.end(), __y.begin());
}
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<pii, pii> piiii;
const int MOD = 1e9+7;
struct modint {
long long val;
modint() = default;
modint(int _val): val(_val){}
modint operator+(modint b){ return ((this->val + b.val)%MOD); }
modint operator-(modint b){ return ((MOD + this->val - b.val)%MOD); }
modint operator*(modint b){ return ((this->val * b.val)%MOD); }
modint operator^(int a){
if(a==0)return 1;
if(a==1)return *this;
return (((*this)*(*this))^(a>>1))*((*this)^(a&1));
}
};
modint invert(modint a){
return a^(MOD-2);
}
modint operator/(modint a, modint b){
return a*invert(b);
}
struct segment_tree_1 {
long long n;
typedef int T;
vector<T> seg;
const T e = 0;
T merge(T a, T b){
if(a==e)return b;
if(b==e)return a;
return max(a,b);
}
segment_tree_1(long long _n): n(_n),seg(4*_n+10,e) /** BUG: GCC does not initialize the elements properly this way */ {
for(auto &i:seg)i=e;
}
void update(long long pos, long long l, long long r, long long idx, T val){
if(r<idx)return;
if(l>idx)return;
if(l==r){
// Merge logic...
seg[pos]=val;
return;
}
update(pos*2+1,l,(l+r)/2,idx,val);
update(pos*2+2,((l+r)/2)+1,r,idx,val);
seg[pos]=merge(seg[pos*2+1],seg[pos*2+2]);
}
T query(long long pos, long long l, long long r, long long ql, long long qr){
if(l > qr)return e;
if(ql > r)return e;
if(ql <= l && r <= qr)return seg[pos];
if(l==r)return e;
return merge(query(pos*2+1,l,(l+r)/2,ql,qr),query(pos*2+2,((l+r)/2)+1,r,ql,qr));
}
};
struct segment_tree_2 {
long long n;
typedef long long T;
vector<T> seg;
const T e = 1;
T merge(T a, T b){
if(a==e)return b;
if(b==e)return a;
return (a*b)%MOD;
}
segment_tree_2(long long _n): n(_n),seg(4*_n+10,e) /** BUG: GCC does not initialize the elements properly this way */ {
for(auto &i:seg)i=e;
}
void update(long long pos, long long l, long long r, long long idx, T val){
if(r<idx)return;
if(l>idx)return;
if(l==r){
seg[pos]=val%MOD;
return;
}
update(pos*2+1,l,(l+r)/2,idx,val);
update(pos*2+2,((l+r)/2)+1,r,idx,val);
seg[pos]=merge(seg[pos*2+1],seg[pos*2+2]);
}
T query(long long pos, long long l, long long r, long long ql, long long qr){
if(l > qr)return e;
if(ql > r)return e;
if(ql <= l && r <= qr)return seg[pos];
if(l==r)return e;
return merge(query(pos*2+1,l,(l+r)/2,ql,qr),query(pos*2+2,((l+r)/2)+1,r,ql,qr));
}
};
int N;
set<int> s1, s2;
segment_tree_1 y(0);
segment_tree_2 x(0);
int init(int N, int X[], int Y[]) {
::N = N;
long long ans=0;
bool run_mod=false;
REP(i,0,N){
auto ix=N-i-1;
if(!run_mod)ans=max<long long>(ans,Y[ix]);
ans*=X[ix];
if(ans>=(1e9+7))ans%=(long long)(1e9+7),run_mod=true;
}
y.n=N+20;
y.seg.resize(4*y.n+10);
for(auto &i:y.seg)i=y.e;
x.n=N+20;
x.seg.resize(4*x.n+10);
for(auto &i:x.seg)i=x.e;
REP(i,0,N){
x.update(0,0,N,i,X[i]);
y.update(0,0,N,i,Y[i]);
}
REP(i,0,N){
if(X[i]>1)s2.insert(i);
}
while(s1.size() < 30 && s2.size()){
s1.insert(*s2.rbegin());
s2.erase(*s2.rbegin());
}
while(s1.size() && s2.size() && *s2.rbegin() > *s1.begin()){
int a=*s2.rbegin();
int b=*s1.begin();
s1.insert(a);
s2.insert(b);
s1.erase(b);
s2.erase(a);
}
return ans;
}
int updateX(int pos, int val) {
x.update(0,0,N,pos,val);
if(val == 1)s1.erase(pos),s2.erase(pos);
else {
if(!s1.count(pos) && !s2.count(pos))s2.insert(pos);
}
while(s1.size() < 30 && s2.size()){
s1.insert(*s2.rbegin());
s2.erase(*s2.rbegin());
}
while(*s2.rbegin() > *s1.begin()){
int a=*s2.rbegin();
int b=*s1.begin();
s1.insert(a);
s2.insert(b);
s1.erase(b);
s2.erase(a);
}
long long ans=0;
bool run_mod=false;
if(s1.size()){
auto it = s1.rbegin();
for(;it!=s1.rend();it++){
if(!run_mod){
ans=max<long long>(ans,y.query(0,0,N,*it,N));
}
ans*=x.query(0,0,N,*it,*it);
if(ans>MOD)run_mod=true,ans%=MOD;
}
}
if(!run_mod)ans=max(ans,y.query(0,0,N,0,N));
if(s2.size()){
ans *= x.query(0,0,N,0,*s2.rbegin());
ans%=MOD;
}
return ans;
}
int updateY(int pos, int val) {
y.update(0,0,N,pos,val);
long long ans=0;
bool run_mod=false;
if(s1.size()){
auto it = s1.rbegin();
for(;it!=s1.rend();it++){
if(!run_mod){
ans=max<long long>(ans,y.query(0,0,N,*it,N));
}
ans*=x.query(0,0,N,*it,*it);
if(ans>MOD)run_mod=true,ans%=MOD;
}
}
if(!run_mod)ans=max(ans,y.query(0,0,N,0,N));
if(s2.size()){
ans *= x.query(0,0,N,0,*s2.rbegin());
ans%=MOD;
}
return ans;
}