# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
584224 | hibiki | 말 (IOI15_horses) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// #include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007;
#define pb push_back
int n, x[500005], y[500005];
set<int, greater<int>> s;
struct node
{
long long val;
node *l, *r;
} *root1, *root2;
node* build1(int l,int r)
{
node *ptr = new node;
if(l == r)
{
ptr->val = x[l];
return ptr;
}
int mid = (l + r) / 2;
ptr->l = build1(l, mid);
ptr->r = build1(mid + 1, r);
ptr->val = ptr->l->val * ptr->r->val;
ptr->val %= mod;
return ptr;
}
node* build2(int l,int r)
{
node *ptr = new node;
if(l == r)
{
ptr->val = y[l];
return ptr;
}
int mid = (l + r) / 2;
ptr->l = build2(l, mid);
ptr->r = build2(mid + 1, r);
ptr->val = max(ptr->l->val, ptr->r->val);
return ptr;
}
int ll,rr;
long long que1(node *ptr, int l,int r)
{
if(ll <= l && r <= rr) return ptr->val;
if(r < ll || rr < l) return 1;
int mid = (l + r) / 2;
return (que1(ptr->l, l, mid) * que1(ptr->r, mid + 1, r)) % mod;
}
int que2(node *ptr, int l,int r)
{
if(ll <= l && r <= rr) return ptr->val;
if(r < ll || rr < l) return 0;
int mid = (l + r) / 2;
return max(que2(ptr->l, l, mid),que2(ptr->r, mid + 1, r));
}
int up_po,up_val;
void up1(node *ptr, int l,int r)
{
if(l == r)
{
ptr->val = up_val;
return ;
}
int mid = (l + r) / 2;
if(up_po <= mid) up1(ptr->l, l, mid);
else up1(ptr->r, mid + 1, r);
ptr->val = ptr->l->val * ptr->r->val;
ptr->val %= mod;
}
void up2(node *ptr, int l,int r)
{
if(l == r)
{
ptr->val = up_val;
return ;
}
int mid = (l + r) / 2;
if(up_po <= mid) up2(ptr->l, l, mid);
else up2(ptr->r, mid + 1, r);
ptr->val = max(ptr->l->val, ptr->r->val);
}