| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 483937 | Cross_Ratio | 말 (IOI15_horses) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
const int p = 1e9 + 7;
typedef pair<int,int> P;
struct SegTree {
vector<int> seg1, seg2, seg3;
int MAX;
void init(int N) {
int i;
for(i=2;i<2*N;i*=2) {}
MAX = i;
seg1.resize(i);
seg2.resize(i);
seg3.resize(i);
}
void cons() {
for(int i=MAX/2-1;i>=1;i--) {
seg1[i] = max(seg1[2*i],seg1[2*i+1]);
seg2[i] = max(seg2[2*i],seg2[2*i+1]);
seg3[i] = 1LL * seg3[2*i] * seg3[2*i+1] % p;
}
}
void update(int n) {
n += MAX/2;
n /= 2;
while(n) {
seg1[n] = max(seg1[2*n],seg1[2*n+1]);
seg2[n] = max(seg2[2*n],seg2[2*n+1]);
seg3[n] = 1LL * seg3[2*n] * seg3[2*n+1] % p;
n /= 2;
}
}
int sum1(int s, int e, int n, int ns, int ne) {
if(e<=ns||ne<=s) return 0;
if(s<=ns&&ne<=e) return seg1[n];
int mid = ns + ne >> 1;
return max(sum1(s,e,2*n,ns,mid),sum1(s,e,2*n+1,mid,ne));
}
int sum2(int s, int e, int n, int ns, int ne) {
if(e<=ns||ne<=s) return 0;
if(s<=ns&&ne<=e) return seg2[n];
int mid = ns + ne >> 1;
return max(sum2(s,e,2*n,ns,mid),sum2(s,e,2*n+1,mid,ne));
}
int sum3(int s, int e, int n, int ns, int ne) {
if(e<=ns||ne<=s) return 1;
if(s<=ns&&ne<=e) return seg3[n];
int mid = ns + ne >> 1;
return 1LL * sum3(s,e,2*n,ns,mid)*sum3(s,e,2*n+1,mid,ne) % p;
}
int sum1(int s, int e) {
if(s >= e) return 0;
return sum1(s, e, 1, 0, MAX/2);
}
int sum2(int s, int e) {
if(s >= e) return 0;
return sum2(s, e, 1, 0, MAX/2);
}
int sum3(int s, int e) {
if(s >= e) return 1;
return sum3(s, e, 1, 0, MAX/2);
}
void Edit(int t, int n, int a) {
if(t == 1) {
seg1[n+MAX/2] = a;
seg3[n+MAX/2] = a;
}
if(t == 2) seg2[n+MAX/2] = a;
update(n);
}
P get_left(int k) {
int s = 0, e = k+1;
while(s + 1 < e) {
int mid = s + e >> 1;
if(sum1(mid,k)==1) {
if(seg1[mid-1+MAX/2] >= 2) {
s = mid;
break;
}
else e = mid;
}
else s = mid;
}
return P(s,sum2(s,k));
}
};
SegTree tree;
int N;
vector<int> X, Y;
int init(int N2, int X2[], int Y2[]) {
N = N2;
for(int i = 0; i < N;i++) {
X.push_back(X2[i]);
Y.push_back(Y2[i]);
}
tree.init(N+5);
//cout << "st\n";
int MAX = tree.MAX;
int i, j;
for(i=0;i<N;i++) {
tree.seg1[i+MAX/2] = X[i];
tree.seg2[i+MAX/2] = Y[i];
tree.seg3[i+MAX/2] = X[i];
}
tree.cons();
//cout <<"st2\n";
long long int cnt = 1;
int pt = N;
long long int macnt = 1;
int ma = 0;
int ans = 0;
while(pt >= 0 && cnt <= 1e9) {
P k = tree.get_left(pt);
//cout << pt << ' ' <<k.first << ' ' << k.second << '\n';
pt = k.first - 1;
if(macnt * k.second > cnt * ma) {
//cout << "E1\n";
macnt = cnt;
ma = k.second;
ans = 1LL * tree.sum3(0,pt+1) * k.second % p;
}
if(pt < 0) break;
if(macnt * Y[pt] > cnt * ma) {
//cout << "E2\n";
macnt = cnt;
ma = Y[pt];
ans = 1LL * tree.sum3(0,pt+1) * Y[pt] % p;
}
cnt *= X[pt];
//cout <<pt << ' ' << ans << '\n';
}
return ans;
}
int updateX(int pos, int val) {
tree.Edit(1,pos,val);
X[pos-1] = val;
long long int cnt = 1;
int pt = N;
long long int macnt = 1;
int ma = 0;
int ans = 0;
while(pt >= 0 && cnt <= 1e9) {
P k = tree.get_left(pt);
//cout << pt << ' ' <<k.first << ' ' << k.second << '\n';
pt = k.first - 1;
if(macnt * k.second > cnt * ma) {
//cout << "E1\n";
macnt = cnt;
ma = k.second;
ans = 1LL * tree.sum3(0,pt+1) * k.second % p;
}
if(pt < 0) break;
if(macnt * Y[pt] > cnt * ma) {
//cout << "E2\n";
macnt = cnt;
ma = Y[pt];
ans = 1LL * tree.sum3(0,pt+1) * Y[pt] % p;
}
cnt *= X[pt];
//cout <<pt << ' ' << ans << '\n';
}
return ans;
}
int updateY(int pos, int val) {
tree.Edit(2, pos, val);
Y[pos-1] = val
long long int cnt = 1;
int pt = N;
long long int macnt = 1;
int ma = 0;
int ans = 0;
while(pt >= 0 && cnt <= 1e9) {
P k = tree.get_left(pt);
//cout << pt << ' ' <<k.first << ' ' << k.second << '\n';
pt = k.first - 1;
if(macnt * k.second > cnt * ma) {
//cout << "E1\n";
macnt = cnt;
ma = k.second;
ans = 1LL * tree.sum3(0,pt+1) * k.second % p;
}
if(pt < 0) break;
if(macnt * Y[pt] > cnt * ma) {
//cout << "E2\n";
macnt = cnt;
ma = Y[pt];
ans = 1LL * tree.sum3(0,pt+1) * Y[pt] % p;
}
cnt *= X[pt];
//cout <<pt << ' ' << ans << '\n';
}
return ans;
}